Practical Experience with Stable Set and Coloring Relaxations

Dunja Pucher, Franz Rendl

Published 2024-01-30, updated 2024-08-26Version 2

Stable Set and Graph Coloring belong to the class of NP-hard optimization problems on graphs. It is well known that even near-optimal solutions for these problems are difficult to find in polynomial time. The Lov\'asz theta function, introduced by Lov\'asz in the late 1970s, provides a powerful tool in the study of these problems. It can be expressed as the optimal value of a semidefinite program and serves as a relaxation for both problems. Considerable effort has been devoted to investigating additional cutting planes to strengthen these relaxations. In our work, we use these models and consider new classes of cutting planes based on small cliques and cycles contained in the underlying graph. We demonstrate that identifying such violated constraints can be done efficiently and that they often lead to significant improvements over previous bounds. However, our computational experiments also show that the quality of these improvements may decrease with problem size, and in some instances, no improvement is observed.