Optimization Online


The extreme points of QSTAB(G) and its implications

Arie M.C.A. Koster (koster***at***zib.de)
Annegret K. Wagler (wagler***at***imo.math.uni-magdeburg.de)

Abstract: Perfect graphs constitute a well-studied 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 anti-blocking 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 anti-blocking polyhedra to a complete characterization of the extreme points of QSTAB(G) by establishing a 1-1 correspondence to the facet-defining 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 (0-1 Programming )

Citation: ZIB-Report 06-30, Zuse Institute Berlin, Germany. June 2006.

Download: [PDF]

Entry Submitted: 06/02/2006
Entry Accepted: 06/02/2006
Entry Last Modified: 06/02/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society