Computational Experience with Stable Set Relaxations

Gerald Gruber, Franz Rendl

We investigate relaxations for the maximum stable set problem based on the Lovasz number $\vartheta (G)$ as an initial upper bound. We strengthen this relaxation by adding two classes of cutting planes, odd circuit and triangle inequalities. We present computational results using this tighter model on many classes of graphs.

Research Report, Department of Mathematics, University of Klagenfurt, Austria, December 2000