Lauria, Massimo ;
Nordström, Jakob
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases
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. '96, Alekhnovich et al. '02] 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. '08, '09, '11, '15] based on Hilbert's Nullstellensatz proofs for a slightly different encoding, thus resolving an open problem mentioned, e.g., in [De Loera et al. '09] and [Li et al. '16]. 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 '15] with a reduction from FPHP to kcolouring derivable by polynomial calculus in constant degree.
BibTeX  Entry
@InProceedings{lauria_et_al:LIPIcs:2017:7541,
author = {Massimo Lauria and Jakob Nordstr{\"o}m},
title = {{Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gr{\"o}bner Bases}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {2:12:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7541},
URN = {urn:nbn:de:0030drops75410},
doi = {10.4230/LIPIcs.CCC.2017.2},
annote = {Keywords: proof complexity, Nullstellensatz, Gr{\"o}bner basis, polynomial calculus, cutting planes, colouring}
}
2017
Keywords: 

proof complexity, Nullstellensatz, Gröbner basis, polynomial calculus, cutting planes, colouring 
Seminar: 

32nd Computational Complexity Conference (CCC 2017)

Issue date: 

2017 
Date of publication: 

2017 