On Extracting Maximum Stable Sets in Perfect Graphs Using Lovász's Theta Function |
| |
Authors: | E Alper Yildirim Xiaofei Fan-Orzechowski |
| |
Institution: | (1) Department of Industrial Engineering, Bilkent University, 06800 Bilkent, Ankara, Turkey;(2) Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, New York;(3) Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY, USA. |
| |
Abstract: | We study the maximum stable set problem. For a given graph, we establish several transformations among feasible solutions
of different formulations of Lovász's theta function. We propose reductions from feasible solutions corresponding to a graph
to those corresponding to its induced subgraphs. We develop an efficient, polynomial-time algorithm to extract a maximum stable
set in a perfect graph using the 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.
This work was supported in part by NSF through CAREER Grant DMI-0237415. Part of this work was performed while the first author
was at the Department of Applied Mathematics and Statisticsat Stony Brook University, Stony Brook, NY, USA. |
| |
Keywords: | maximum stable sets Lovász's theta function semidefinite programming perfect graphs |
本文献已被 SpringerLink 等数据库收录! |
|