Document Open Access Logo

Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases

Authors Massimo Lauria, Jakob Nordström

PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.2.pdf
  • Filesize: 0.59 MB
  • 20 pages

Document Identifiers

Author Details

Massimo Lauria
Jakob Nordström

Cite AsGet BibTex

Massimo Lauria and Jakob Nordström. Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.CCC.2017.2

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. '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.
Keywords
  • proof complexity
  • Nullstellensatz
  • Gröbner basis
  • polynomial calculus
  • cutting planes
  • colouring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, and Avi Wigderson. Space complexity in propositional calculus. SIAM Journal on Computing, 31(4):1184-1211, 2002. Preliminary version in STOC'00. Google Scholar
  2. Michael Alekhnovich and Alexander A. Razborov. Lower bounds for polynomial calculus: Non-binomial case. Proceedings of the Steklov Institute of Mathematics, 242:18-35, 2003. Available at http://people.cs.uchicago.edu/~razborov/files/misha.pdf. Preliminary version in FOCS'01.
  3. Noga Alon and Michael Tarsi. Colorings and orientations of graphs. Combinatorica, 12(2):125-134, June 1992. Google Scholar
  4. Roberto J. Bayardo Jr. and Robert Schrag. Using CSP look-back techniques to solve real-world SAT instances. In Proceedings of the 14th National Conference on Artificial Intelligence (AAAI'97), pages 203-208, July 1997. Google Scholar
  5. David Allen Bayer. The Division Algorithm and the Hilbert Scheme. PhD thesis, Harvard University, Cambridge, MA, USA, June 1982. Available at URL: https://www.math.columbia.edu/~bayer/papers/Bayer-thesis.pdf.
  6. Paul Beame, Joseph C. Culberson, David G. Mitchell, and Cristopher Moore. The resolution complexity of random graph k-colorability. Discrete Applied Mathematics, 153(1-3):25-47, December 2005. Google Scholar
  7. Paul Beame, Russell Impagliazzo, Jan Krajíček, Toniann Pitassi, and Pavel Pudlák. Lower bounds on Hilbert’s Nullstellensatz and propositional proofs. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS'94), pages 794-806, November 1994. Google Scholar
  8. Richard Beigel and David Eppstein. 3-coloring in time O(n^1.3289). Journal of Algorithms, 54(2):168-204, February 2005. Google Scholar
  9. Eli Ben-Sasson and Russell Impagliazzo. Random CNF’s are hard for the polynomial calculus. Computational Complexity, 19:501-519, 2010. Preliminary version in FOCS'99. Google Scholar
  10. Eli Ben-Sasson and Avi Wigderson. Short proofs are narrow - resolution made simple. Journal of the ACM, 48(2):149-169, March 2001. Preliminary version in STOC'99. Google Scholar
  11. Archie Blake. Canonical Expressions in Boolean Algebra. PhD thesis, University of Chicago, 1937. Google Scholar
  12. Samuel R. Buss and Peter Clote. Cutting planes, connectivity and threshold logic. Archive for Mathematical Logic, 35:33-63, 1996. Google Scholar
  13. Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, and Toniann Pitassi. Linear gaps between degrees for the polynomial calculus modulo distinct primes. Journal of Computer and System Sciences, 62(2):267-289, March 2001. Preliminary version in CCC'99. Google Scholar
  14. Vašek Chvátal. Edmond polytopes and a hierarchy of combinatorial problems. Discrete Mathematics, 4(1):305-337, 1973. Google Scholar
  15. Matthew Clegg, Jeffery Edmonds, and Russell Impagliazzo. Using the Groebner basis algorithm to find proofs of unsatisfiability. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC'96), pages 174-183, May 1996. Google Scholar
  16. William Cook, Collette Rene Coullard, and György Turán. On the complexity of cutting-plane proofs. Discrete Applied Mathematics, 18(1):25-38, November 1987. Google Scholar
  17. Jesús A. De Loera. Gröbner bases and graph colorings. Beiträge zur Algebra und Geometrie, 36(1):89-96, January 1995. Available at URL: https://www.emis.de/journals/BAG/vol.36/no.1/.
  18. Jesús A. De Loera, Susan Margulies, Michael Pernpeintner, Eric Riedl, David Rolnick, Gwen Spencer, Despina Stasi, and Jon Swenson. Graph-coloring ideals: Nullstellensatz certificates, Gröbner bases for chordal graphs, and hardness of Gröbner bases. In Proceedings of the 40th International Symposium on Symbolic and Algebraic Computation (ISSAC'15), pages 133-140, July 2015. Google Scholar
  19. Jesús A. De Loera, Jon Lee, Peter N. Malkin, and Susan Margulies. Hilbert’s Nullstellensatz and an algorithm for proving combinatorial infeasibility. In Proceedings of the 21st International Symposium on Symbolic and Algebraic Computation (ISSAC'08), pages 197-206, July 2008. Google Scholar
  20. Jesús A. De Loera, Jon Lee, Peter N. Malkin, and Susan Margulies. Computing infeasibility certificates for combinatorial problems through Hilbert’s Nullstellensatz. Journal of Symbolic Computation, 46(11):1260-1283, November 2011. Google Scholar
  21. Jesús A. De Loera, Jon Lee, Susan Margulies, and Shmuel Onn. Expressing combinatorial problems by systems of polynomial equations and Hilbert’s Nullstellensatz. Combinatorics, Probability and Computing, 18:551-582, July 2009. Google Scholar
  22. Nicola Galesi and Massimo Lauria. On the automatizability of polynomial calculus. Theory of Computing Systems, 47:491-506, August 2010. Google Scholar
  23. Nicola Galesi and Massimo Lauria. Optimality of size-degree trade-offs for polynomial calculus. ACM Transactions on Computational Logic, 12:4:1-4:22, November 2010. Google Scholar
  24. Ralph E. Gomory. An algorithm for integer solutions of linear programs. In R.L. Graves and P. Wolfe, editors, Recent Advances in Mathematical Programming, pages 269-302. McGraw-Hill, New York, 1963. Google Scholar
  25. Christopher J. Hillar and Troels Windfeldt. Algebraic characterization of uniquely vertex colorable graphs. Journal of Combinatorial Theory, Series B, 98(2):400-414, March 2008. Google Scholar
  26. Thore Husfeldt. Graph colouring algorithms. In Lowell W. Beineke and Robin J. Wilson, editors, Topics in Chromatic Graph Theory, Encyclopedia of Mathematics and its Applications, chapter 13, pages 277-303. Cambridge University Press, May 2015. Google Scholar
  27. Russell Impagliazzo, Pavel Pudlák, and Jiří Sgall. Lower bounds for the polynomial calculus and the Gröbner basis algorithm. Computational Complexity, 8(2):127-144, 1999. Google Scholar
  28. Serge Lang. Algebra. Springer New York, 2005. Google Scholar
  29. Daniel Le Berre and Anne Parrain. The Sat4j library, release 2.2. Journal on Satisfiability, Boolean Modeling and Computation, 7:59-64, 2010. Google Scholar
  30. Bo Li, Benjamin Lowenstein, and Mohamed Omar. Low degree Nullstellensatz certificates for 3-colorability. The Electronic Journal of Combinatorics, 23(1), January 2016. Google Scholar
  31. László Lovász. Stable sets and polynomials. Discrete Mathematics, 124(1-3):137-153, January 1994. Google Scholar
  32. João P. Marques-Silva and Karem A. Sakallah. GRASP: A search algorithm for propositional satisfiability. IEEE Transactions on Computers, 48(5):506-521, May 1999. Preliminary version in ICCAD'96. Google Scholar
  33. Yuri V. Matiyasevich. A criterion for vertex colorability of a graph stated in terms of edge orientations. Diskretnyi Analiz, 26:65-71, 1974. English translation of the Russian original. Available at URL: http://logic.pdmi.ras.ru/~yumat/papers/22_paper/.
  34. Yuri V. Matiyasevich. Some algebraic methods for calculating the number of colorings of a graph. Journal of Mathematical Sciences, 121(3):2401-2408, May 2004. Google Scholar
  35. Colin McDiarmid. Colouring random graphs. Annals of Operations Research, 1(3):183-200, October 1984. Google Scholar
  36. Mladen Mikša and Jakob Nordström. A generalized method for proving polynomial calculus degree lower bounds. In Proceedings of the 30th Annual Computational Complexity Conference (CCC'15), volume 33 of Leibniz International Proceedings in Informatics (LIPIcs), pages 467-487, June 2015. Google Scholar
  37. Michal Mnuk. Representing graph properties by polynomial ideals. In Proceedings of the 4th International Workshop on Computer Algebra in Scientific Computing (CASC'01), pages 431-444, September 2001. Google Scholar
  38. Matthew W. Moskewicz, Conor F. Madigan, Ying Zhao, Lintao Zhang, and Sharad Malik. Chaff: Engineering an efficient SAT solver. In Proceedings of the 38th Design Automation Conference (DAC'01), pages 530-535, June 2001. Google Scholar
  39. Pseudo-Boolean competition 2016: Results by benchmark for category no optimisation, small integers, linear constraints (DEC-SMALLINT-LIN). http://www.cril.univ-artois.fr/PB16/results/globalbybench.php?idev=81&idcat=47, 2016.
  40. Sat4j: The Boolean satisfaction and optimization library in Java. URL: http://www.sat4j.org/.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact