On Extracting Maximum Stable Sets
in Perfect Graphs Using
Lov'asz's Theta Function
by
Emre Alper Yildirim
Bilkent University
We study the maximum stable set problem. For a given graph, we develop an
efficient, polynomial-time algorithm to extract a maximum stable set in a
perfect graph using Lov'asz's theta function. Our algorithm iteratively
transforms an approximate solution of the semidefinite formulation of the theta
function into an approximate solution of another formulation, which is then used
to identify a vertex that belongs to a maximum stable set. The subgraph induced
by that vertex and its neighbors is removed and the same procedure is repeated
on successively smaller graphs. We establish that solving the theta problem up
to an adaptively chosen, fairly rough accuracy suffices in order for the
algorithm to work properly. Furthermore, our algorithm successfully employs a
warm-start strategy to recompute the theta function on smaller subgraphs.
Computational results demonstrate that our algorithm can efficiently extract
maximum stable sets in comparable time it takes to solve the theta problem on
the original graph to optimality.
The talk will be mostly self-contained, describing the derivation of Lov'asz's
theta function. No background will be assumed.
This is joint work with Xiaofei Fan-Orzechowski, Department of Applied
Mathematics and Statistics, Stony Brook University.