Publication Date:
2021-03-16
Description:
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 {\em 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 {\em 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:
ddc:000
Language:
English
Type:
reportzib
,
doc-type:preprint
Format:
application/pdf
Format:
application/postscript
