  


The extreme points of QSTAB(G) and its implications
Arie M.C.A. Koster (kosterzib.de) Abstract: Perfect graphs constitute a wellstudied graph class with a rich structure, reflected by many characterizations w.r.t different concepts. Perfect graphs are, e.g., characterized as precisely those graphs G where the stable set polytope STAB(G) coincides with the clique constraint stable set polytope QSTAB(G). For all imperfect graphs STAB(G) \subset QSTAB(G) holds and, therefore, it is natural to measure imperfection in terms of the difference between STAB(G) and QSTAB(G). Several concepts have been developed in this direction, for instance the dilation ratio of STAB(G) and QSTAB(G) which is equivalent to the imperfection ratio imp(G) of G. To determine imp(G), both knowledge on the facets of STAB(G) and the extreme points of QSTAB(G) is required. The antiblocking theory of polyhedra yields all dominating extreme points of QSTAB(G), provided a complete description of the facets of STAB(\overline G) is known. As this is typically not the case, we extend the result on antiblocking polyhedra to a complete characterization of the extreme points of QSTAB(G) by establishing a 11 correspondence to the facetdefining subgraphs of \overline G. We discuss several consequences, in particular, we give alternative proofs of several famous results. Keywords: stable set polytope, fractional stable set polytope, imperfection ratio Category 1: Combinatorial Optimization (Polyhedra ) Category 2: Combinatorial Optimization (Graphs and Matroids ) Category 3: Integer Programming (01 Programming ) Citation: ZIBReport 0630, Zuse Institute Berlin, Germany. June 2006. Download: [PDF] Entry Submitted: 06/02/2006 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  