Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases
(2017) 32nd Computational Complexity Conference, CCC 2017 In Leibniz International Proceedings in Informatics, LIPIcs 79.- 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ö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... (More)
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.
(Less)
- author
- Lauria, Massimo and Nordström, Jakob LU
- publishing date
- 2017-07-01
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- 3-colouring, Cutting planes, Gröbner basis, Nullstellensatz, Polynomial calculus, Proof complexity
- host publication
- 32nd Computational Complexity Conference, CCC 2017
- series title
- Leibniz International Proceedings in Informatics, LIPIcs
- editor
- O'Donnell, Ryan
- volume
- 79
- article number
- 2
- publisher
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik
- conference name
- 32nd Computational Complexity Conference, CCC 2017
- conference location
- Riga, Latvia
- conference dates
- 2017-07-06 - 2017-07-09
- external identifiers
-
- scopus:85028777140
- ISSN
- 1868-8969
- ISBN
- 9783959770408
- DOI
- 10.4230/LIPIcs.CCC.2017.2
- language
- English
- LU publication?
- no
- id
- ca09319e-2f47-41d6-88d5-f875ed2677db
- date added to LUP
- 2020-12-18 22:20:04
- date last changed
- 2022-04-19 03:06:48
@inproceedings{ca09319e-2f47-41d6-88d5-f875ed2677db,
abstract = {{<p>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.</p>}},
author = {{Lauria, Massimo and Nordström, Jakob}},
booktitle = {{32nd Computational Complexity Conference, CCC 2017}},
editor = {{O'Donnell, Ryan}},
isbn = {{9783959770408}},
issn = {{1868-8969}},
keywords = {{3-colouring; Cutting planes; Gröbner basis; Nullstellensatz; Polynomial calculus; Proof complexity}},
language = {{eng}},
month = {{07}},
publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
series = {{Leibniz International Proceedings in Informatics, LIPIcs}},
title = {{Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases}},
url = {{http://dx.doi.org/10.4230/LIPIcs.CCC.2017.2}},
doi = {{10.4230/LIPIcs.CCC.2017.2}},
volume = {{79}},
year = {{2017}},
}