Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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ö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öm 2015] with a reduction from FPHP to k-colouring derivable by polynomial calculus in constant degree.
Originalsprog | Engelsk |
---|---|
Titel | 32nd Computational Complexity Conference, CCC 2017 |
Redaktører | Ryan O'Donnell |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 1 jul. 2017 |
Artikelnummer | 2 |
ISBN (Elektronisk) | 9783959770408 |
DOI | |
Status | Udgivet - 1 jul. 2017 |
Eksternt udgivet | Ja |
Begivenhed | 32nd Computational Complexity Conference, CCC 2017 - Riga, Letland Varighed: 6 jul. 2017 → 9 jul. 2017 |
Konference
Konference | 32nd Computational Complexity Conference, CCC 2017 |
---|---|
Land | Letland |
By | Riga |
Periode | 06/07/2017 → 09/07/2017 |
Sponsor | Microsoft Research, University of Latvia |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 79 |
ISSN | 1868-8969 |
ID: 251867943