Document Open Access Logo

From Cliques to Colorings and Back Again

Authors Marijn J. H. Heule, Anthony Karahalios , Willem-Jan van Hoeve

PDF
Thumbnail PDF

File

LIPIcs.CP.2022.26.pdf
  • Filesize: 0.64 MB
  • 10 pages

Document Identifiers

Author Details

Marijn J. H. Heule
  • Carnegie Mellon University, Pittsburgh, PA, USA
Anthony Karahalios
  • Carnegie Mellon University, Pittsburgh, PA, USA
Willem-Jan van Hoeve
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

  • Heule, Marijn J. H.: Partially supported by NSF under grant CCF-2006363.
  • Karahalios, Anthony: Partially supported by Office of Naval Research Grant No. N00014-21-1-2240.
  • van Hoeve, Willem-Jan: Partially supported by Office of Naval Research Grant No. N00014-21-1-2240 and National Science Foundation Award #1918102.

Cite As Get BibTex

Marijn J. H. Heule, Anthony Karahalios, and Willem-Jan van Hoeve. From Cliques to Colorings and Back Again. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 26:1-26:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CP.2022.26

Abstract

We present an exact algorithm for graph coloring and maximum clique problems based on SAT technology. It relies on four sub-algorithms that alternatingly compute cliques of larger size and colorings with fewer colors. We show how these techniques can mutually help each other: larger cliques facilitate finding smaller colorings, which in turn can boost finding larger cliques. We evaluate our approach on the DIMACS graph coloring suite. For finding maximum cliques, we show that our algorithm can improve the state-of-the-art MaxSAT-based solver IncMaxCLQ, and for the graph coloring problem, we close two open instances, decrease two upper bounds, and increase one lower bound.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
  • Mathematics of computing → Graph coloring
Keywords
  • Graph coloring
  • maximum clique
  • Boolean satisfiability

Metrics

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

Supplementary Materials

References

  1. D. Brélaz. New methods to color the vertices of a graph. Communications of the ACM, 22(4):251-256, 1979. Google Scholar
  2. Shawn T. Brown, Paola Buitrago, Edward Hanna, Sergiu Sanielevici, Robin Scibek, and Nicholas A. Nystrom. Bridges-2: A Platform for Rapidly-Evolving and Data Intensive Research, pages 1-4. Association for Computing Machinery, New York, NY, USA, 2021. URL: https://doi.org/10.1145/3437359.3465593.
  3. Armin Biere Katalin Fazekas Mathias Fleury and Maximilian Heisinger. Cadical, kissat, paracooba, plingeling and treengeling entering the sat competition 2020. SAT COMPETITION, 2020:50, 2020. Google Scholar
  4. Stefano Gualandi and Federico Malucelli. Exact solution of graph coloring problems via constraint programming and column generation. INFORMS Journal on Computing, 24(1):81-100, 2012. Google Scholar
  5. Youssef Hamadi, Said Jabbour, and Lakhdar Sais. Manysat: a parallel sat solver. Journal on Satisfiability, Boolean Modeling and Computation, 6(4):245-262, 2010. Google Scholar
  6. Emmanuel Hébrard and George Katsirelos. Constraint and satisfiability reasoning for graph coloring. Journal of Artificial Intelligence Research, 69:33-65, 2020. Google Scholar
  7. S. Held, W. Cook, and E. C. Sewell. Maximum-weight stable sets and safe lower bounds for graph coloring. Mathematical Programming Computation, 4(4):363-381, 2012. Google Scholar
  8. Stephan Held, William Cook, and Edward C Sewell. Safe lower bounds for graph coloring. In International Conference on Integer Programming and Combinatorial Optimization, pages 261-273. Springer, 2011. Google Scholar
  9. Abdelraouf Ishtaiwi, John Thornton, Abdul Sattar, and Duc Nghia Pham. Neighbourhood clause weight redistribution in local search for sat. In Peter van Beek, editor, Principles and Practice of Constraint Programming - CP 2005, pages 772-776, Berlin, Heidelberg, 2005. Springer. Google Scholar
  10. Matti Järvisalo, Armin Biere, and Marijn Heule. Blocked clause elimination. In Javier Esparza and Rupak Majumdar, editors, Tools and Algorithms for the Construction and Analysis of Systems, 16th International Conference, TACAS 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010, Paphos, Cyprus, March 20-28, 2010. Proceedings, volume 6015 of Lecture Notes in Computer Science, pages 129-144. Springer, 2010. Google Scholar
  11. David S Johnson and Michael A Trick. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11-13, 1993, volume 26. American Mathematical Soc., 1996. Google Scholar
  12. Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, 1972. Google Scholar
  13. Chu-Min Li, Zhiwen Fang, and Ke Xu. Combining maxsat reasoning and incremental upper bound for the maximum clique problem. In 2013 IEEE 25th International Conference on Tools with Artificial Intelligence, pages 939-946. IEEE, 2013. Google Scholar
  14. Shadi Mahmoudi and Shahriar Lotfi. Modified cuckoo optimization algorithm (mcoa) to solve graph coloring problem. Applied soft computing, 33:48-64, 2015. Google Scholar
  15. Enrico Malaguti, Michele Monaci, and Paolo Toth. An exact approach for the vertex coloring problem. Discrete Optimization, 8(2):174-190, 2011. Google Scholar
  16. Enrico Malaguti and Paolo Toth. A survey on vertex coloring problems. International transactions in operational research, 17(1):1-34, 2010. Google Scholar
  17. A. Mehrotra and M. A. Trick. A Column Generation Approach for Graph Coloring. INFORMS Journal on Computing, 8(4):344-354, 1996. Google Scholar
  18. I. Méndez-Díaz and P. Zabala. A Branch-and-Cut algorithm for graph coloring. Discrete Applied Mathematics, 154:826-847, 2006. Google Scholar
  19. Patric RJ Östergård. A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120(1-3):197-207, 2002. Google Scholar
  20. Daniel Porumbel. Projective cutting-planes. SIAM Journal on Optimization, 30(1):1007-1032, 2020. Google Scholar
  21. Jean-Charles Régin. Using Constraint Programming to Solve the Maximum Clique Problem. In Proceedings of CP, pages 634-648, 2003. Google Scholar
  22. Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. Google Scholar
  23. Bart Selman, Henry A. Kautz, and Bram Cohen. Noise strategies for improving local search. In Barbara Hayes-Roth and Richard E. Korf, editors, Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31 - August 4, 1994, Volume 1, pages 337-343. AAAI Press / The MIT Press, 1994. Google Scholar
  24. João P. Marques Silva, Inês Lynce, and Sharad Malik. Conflict-driven clause learning SAT solvers. In Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors, Handbook of Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications, pages 131-153. IOS Press, 2009. Google Scholar
  25. Carsten Sinz. Towards an optimal CNF encoding of boolean cardinality constraints. In International conference on principles and practice of constraint programming, pages 827-831. Springer, 2005. Google Scholar
  26. Wen Sun, Jin-Kao Hao, Yuhao Zang, and Xiangjing Lai. A solution-driven multilevel approach for graph coloring. Applied Soft Computing, 104:107174, 2021. Google Scholar
  27. Olawale Titiloye and Alan Crispin. Graph coloring with a distributed hybrid quantum annealing algorithm. In KES International Symposium on Agent and Multi-Agent Systems: Technologies and Applications, pages 553-562. Springer, 2011. Google Scholar
  28. Olawale Titiloye and Alan Crispin. Quantum annealing of the graph coloring problem. Discrete Optimization, 8(2):376-384, 2011. Google Scholar
  29. Olawale Titiloye and Alan Crispin. Parameter tuning patterns for random graph coloring with quantum annealing. PloS one, 7(11):e50060, 2012. Google Scholar
  30. Dave A. D. Tompkins and Holger H. Hoos. UBCSAT: an implementation and experimentation environment for SLS algorithms for SAT and MAX-SAT. In Holger H. Hoos and David G. Mitchell, editors, Theory and Applications of Satisfiability Testing, 7th International Conference, SAT 2004, Vancouver, BC, Canada, May 10-13, 2004, Revised Selected Papers, volume 3542 of Lecture Notes in Computer Science, pages 306-320. Springer, 2004. Google Scholar
  31. R. P. van der Hulst. A branch-price-and-cut algorithm for graph coloring. Master’s thesis, University of Twente, 2021. Google Scholar
  32. Allen Van Gelder. Another look at graph coloring via propositional satisfiability. Discrete Applied Mathematics, 156(2):230-243, 2008. Google Scholar
  33. Willem-Jan van Hoeve. Graph coloring with decision diagrams. Mathematical Programming, pages 1-44, 2021. Google Scholar
  34. Miroslav N Velev. Exploiting hierarchy and structure to efficiently solve graph coloring as sat. In 2007 IEEE/ACM International Conference on Computer-Aided Design, pages 135-142. IEEE, 2007. Google Scholar
  35. Qinghua Wu and Jin-Kao Hao. Coloring large graphs based on independent set extraction. Computers & Operations Research, 39(2):283-290, 2012. Google Scholar
  36. Qinghua Wu and Jin-Kao Hao. A review on algorithms for maximum clique problems. European Journal of Operational Research, 242(3):693-709, 2015. Google Scholar
  37. Ke Xu. Bhoslib: Benchmarks with hidden optimum solutions for graph problems (maximum clique, maximum independent set, minimum vertex cover and vertex coloring)-hiding exact solutions in random graphs. web site. Web site, http://www.nlsde.buaa.edu.en/~kexu/benchmarks/graphbenchmarks.htm, 2004.
  38. Zhaoyang Zhou, Chu-Min Li, Chong Huang, and Ruchu Xu. An exact algorithm with learning for the graph coloring problem. Computers & operations research, 51:282-301, 2014. Google Scholar
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 About DROPS Imprint Privacy Contact