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

Federico Battista, Fabrizio Rossi, Stefano Smriglio

The Lovász theta function $\theta (G)$ 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 (S…