Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases
Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
Abstract
We consider the graph kcolouring problem encoded as a set of polynomial equations in the standard way. We prove that there are boundeddegree graphs that do not have legal kcolourings 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 kcolouring 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 boundeddegree bipartite graphs in [Miksa and Nordström 2015] with a reduction from FPHP to kcolouring derivable by polynomial calculus in constant degree.
Details
Authors  

External organisations 

Research areas and keywords  Subject classification (UKÄ) – MANDATORY
Keywords

Original language  English 

Title of host publication  32nd Computational Complexity Conference, CCC 2017 
Editors  Ryan O'Donnell 
Publisher  Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing 
ISBN (Electronic)  9783959770408 
Publication status  Published  2017 Jul 1 
Publication category  Research 
Peerreviewed  Yes 
Externally published  Yes 
Event  32nd Computational Complexity Conference, CCC 2017  Riga, Latvia Duration: 2017 Jul 6 → 2017 Jul 9 
Publication series
Name  Leibniz International Proceedings in Informatics, LIPIcs 

Publisher  Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing 
Volume  79 
ISSN (Print)  18688969 
Conference
Conference  32nd Computational Complexity Conference, CCC 2017 

Country  Latvia 
City  Riga 
Period  2017/07/06 → 2017/07/09 