Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding


title = "Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gr{\"o}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. 1996, Alekhnovich et al. 2002] requires linear degree, and hence exponential size, to establish this fact. This implies a linear degree lower bound for any algorithms based on Gr{\"o}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. 2008, 2009, 2011, 2015] based on Hilbert's Nullstellensatz proofs for a slightly different encoding, thus resolving an open problem mentioned, e.g., in [De Loera et al. 2009] and [Li et al. 2016]. 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{\"o}m 2015] with a reduction from FPHP to k-colouring derivable by polynomial calculus in constant degree.",
keywords = "3-colouring, Cutting planes, Gr{\"o}bner basis, Nullstellensatz, Polynomial calculus, Proof complexity",
author = "Massimo Lauria and Jakob Nordstr{\"o}m",
year = "2017",
month = jul,
day = "1",
doi = "10.4230/LIPIcs.CCC.2017.2",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Ryan O'Donnell",
booktitle = "32nd Computational Complexity Conference, CCC 2017",
note = "32nd Computational Complexity Conference, CCC 2017 ; Conference date: 06-07-2017 Through 09-07-2017",