Renato Monteiro
School of Industrial and Systems Engineering
Georgia Institute of Technology

The stability number a(G) for a given graph G is the size of
a maximum stable set in G. The Lovász theta number provides an
upper bound on a(G) and can be computed as the optimal value of
the Lovász semidefinite program. In this paper, we show that
restricting the matrix variable in the Lovász semidefinite program
to be rank-one or rank-two yields a pair of continuous, nonlinear
optimization problems each having the global optimal value
a(G). We propose heuristics for obtaining large stable sets in
G based on these new formulations and present computational results
indicating the effectiveness of the heuristics.