Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases. / Lauria, Massimo; Nordström, Jakob.
32nd Computational Complexity Conference, CCC 2017. ed. / Ryan O'Donnell. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. 2 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 79).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases
AU - Lauria, Massimo
AU - Nordström, Jakob
PY - 2017/7/1
Y1 - 2017/7/1
N2 - 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.
AB - 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.
KW - 3-colouring
KW - Cutting planes
KW - Gröbner basis
KW - Nullstellensatz
KW - Polynomial calculus
KW - Proof complexity
UR - http://www.scopus.com/inward/record.url?scp=85028777140&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CCC.2017.2
DO - 10.4230/LIPIcs.CCC.2017.2
M3 - Article in proceedings
AN - SCOPUS:85028777140
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 32nd Computational Complexity Conference, CCC 2017
A2 - O'Donnell, Ryan
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 32nd Computational Complexity Conference, CCC 2017
Y2 - 6 July 2017 through 9 July 2017
ER -
ID: 251867943