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

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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 [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.

Details

Authors
External organisations
  • Sapienza University of Rome
  • KTH Royal Institute of Technology
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science

Keywords

  • 3-colouring, Cutting planes, Gröbner basis, Nullstellensatz, Polynomial calculus, Proof complexity
Original languageEnglish
Title of host publication32nd Computational Complexity Conference, CCC 2017
EditorsRyan O'Donnell
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770408
Publication statusPublished - 2017 Jul 1
Publication categoryResearch
Peer-reviewedYes
Externally publishedYes
Event32nd Computational Complexity Conference, CCC 2017 - Riga, Latvia
Duration: 2017 Jul 62017 Jul 9

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume79
ISSN (Print)1868-8969

Conference

Conference32nd Computational Complexity Conference, CCC 2017
CountryLatvia
CityRiga
Period2017/07/062017/07/09