License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2017.2
URN: urn:nbn:de:0030-drops-75410
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7541/
Lauria, Massimo ;
Nordström, Jakob
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases
Abstract
We consider the graph k-colouring problem encoded as a set of polynomial equations in the standard way. We prove that there are bounded-degree graphs that do not have legal k-colourings but for which the polynomial calculus proof system defined in [Clegg et al. '96, Alekhnovich et al. '02] requires linear degree, and hence exponential size, to establish this fact. This implies a linear degree lower bound for any algorithms based on Gröbner bases solving graph k-colouring} using this encoding. The same bound applies also for the algorithm studied in a sequence of papers [De Loera et al. '08, '09, '11, '15] based on Hilbert's Nullstellensatz proofs for a slightly different encoding, thus resolving an open problem mentioned, e.g., in [De Loera et al. '09] and [Li et al. '16]. We obtain our results by combining the polynomial calculus degree lower bound for functional pigeonhole principle (FPHP) formulas over bounded-degree bipartite graphs in [Miksa and Nordström '15] with a reduction from FPHP to k-colouring derivable by polynomial calculus in constant degree.
BibTeX - Entry
@InProceedings{lauria_et_al:LIPIcs:2017:7541,
author = {Massimo Lauria and Jakob Nordstr{\"o}m},
title = {{Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gr{\"o}bner Bases}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {2:1--2:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-040-8},
ISSN = {1868-8969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7541},
URN = {urn:nbn:de:0030-drops-75410},
doi = {10.4230/LIPIcs.CCC.2017.2},
annote = {Keywords: proof complexity, Nullstellensatz, Gr{\"o}bner basis, polynomial calculus, cutting planes, colouring}
}
Keywords: |
|
proof complexity, Nullstellensatz, Gröbner basis, polynomial calculus, cutting planes, colouring |
Collection: |
|
32nd Computational Complexity Conference (CCC 2017) |
Issue Date: |
|
2017 |
Date of publication: |
|
01.08.2017 |