From Cliques to Colorings and Back Again
Published in Constraint Programming 2022, 2022
Recommended citation: Heule, Marijn JH, Anthony Karahalios, and Willem-Jan van Hoeve (2022). "From Cliques to Colorings and Back Again." Constraints 2022. https://drops.dagstuhl.de/opus/volltexte/2022/16655/pdf/LIPIcs-CP-2022-26.pdf
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.