2026-07-23T20:15:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7541 2024-03-06T10:40:10Z ddc:004 open_access

Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases Lauria, Massimo Nordström, Jakob proof complexity Nullstellensatz Gröbner basis polynomial calculus cutting planes colouring 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. '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 k-colouring} 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 bounded-degree bipartite graphs in [Miksa and Nordström '15] with a reduction from FPHP to k-colouring derivable by polynomial calculus in constant degree. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Massimo Lauria and Jakob Nordström 2017 Is Part Of LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2017.2 urn:nbn:de:0030-drops-75410 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.2 eng https://creativecommons.org/licenses/by/3.0/legalcode