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.
Citation
ZIB-Report 06-30, Zuse Institute Berlin, Germany. June 2006.