Title: On Extracting Stable Sets from Lov{\'a}sz's Theta
Function

Abstract: We study the maximum stable set problem. We propose algorithms
to extract stable sets in a graph using Lov{\'a}sz's theta function. Our
first algorithm iteratively transforms the optimal solution of the
semidefinite formulation of the theta function into an optimal solution
of another formulation, which is then used to eliminate a subgraph while
maintaining large stable sets, and recomputes the theta function on
successively smaller graphs. For perfect graphs, the algorithm extracts
a maximum stable set in at most $n$ computations of the theta function,
where $n$ is the number of vertices. We show that the same algorithm can
be used to extract large stable sets in non-perfect graphs. We also
propose a simpler heuristic based on only one computation of the theta
function for a given graph. Our computational results demonstrate that
our algorithms can efficiently extract optimal or near-optimal stable sets
from Lov{\'a}sz's theta function.