  


On Extracting Maximum Stable Sets in Perfect Graphs Using Lovasz's Theta Function
E. Alper Yildirim (yildirimams.sunysb.edu) Abstract: We study the maximum stable set problem. For a given graph, we establish several transformations among feasible solutions of different formulations of Lov{\'a}sz's theta function. We propose reductions from feasible solutions corresponding to a graph to those corresponding to its subgraphs. We develop an efficient, polynomialtime 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 warmstart 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. Keywords: Maximum stable set, Lov{\'a}sz's theta function, semidefinite Category 1: Combinatorial Optimization Category 2: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Computational Optimization and Applications, 33 (23) pp. 229247 (2006) Download: Entry Submitted: 10/13/2003 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  