Application of the Lovász-Schrijver Operator to Compact Stable Set Integer Programs

Abstract The Lovász theta function $$\theta (G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>θ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> provides a very good upper bound on the stability number of a graph G . It can be computed in polynomial time by solving a semidefinite program (SDP), which also turns out to be fairly tractable in practice. Consequently, $$\theta (G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>θ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> achieves a hard-to-beat trade-off between computational effort and strength of the bound. Indeed, several attempts to improve the theta bound are documented, mainly based on playing around the application of the $$N_+(\cdot )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>N</mml:mi> <mml:mo>+</mml:mo> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mo>·</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> lifting operator of Lovász and Schrijver to the classical formulation of the maximum stable set problem (SSP). Experience shows that solving such SDPs often struggles against practical intractability and requires highly specialized methods. We investigate the application of such an operator to two different linear formulations of the SSP based on clique and nodal inequalities, respectively. These two formulations are described by fewer inequalities than the natural formulation based on edge inequalities, yet they guarantee that the resulting SDP bound is at least as strong as $$\theta (G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>θ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Our computational experience, including larger graphs than those previously documented, shows that upper bounds stronger than $$\theta (G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>θ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> can be accessed by a reasonable additional effort using the clique-based formulation on sparse graphs and the nodal-based one on dense graphs.