Application of the Lov\'asz-Schrijver Lift-and-Project Operator to
Compact Stable Set Integer Programs
Application of the Lov\'asz-Schrijver Lift-and-Project Operator to
Compact Stable Set Integer Programs
The Lov\'asz 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 (SDP), which also turns out to be fairly tractable in practice. Consequently, $\theta(G)$ achieves a hard-to-beat trade-off between computational …