Practical Experience with Stable Set and Coloring Relaxations

The stable set problem and the graph coloring problem are classes 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ász theta function, introduced by Lovász 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. Over the years, considerable effort has been devoted to investigating additional cutting planes to strengthen these relaxations. In our work, we use these models and consider classes of cutting planes based on cliques, odd cycles, and odd antiholes 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.