id: 05550531
dt: j
an: 05550531
au: Coulonges, Sylvain; Pêcher, Arnaud; Wagler, Annegret K.
ti: Characterizing and bounding the imperfection ratio for some classes of
    graphs.
so: Math. Program. 118, No. 1 (A), 37-46 (2009).
py: 2009
pu: Springer-Verlag, Berlin
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/s10107-007-0182-9
ab: Summary: Perfect graphs constitute a well-studied graph class with a rich
    structure, which is reflected by many characterizations with respect to
    different concepts. Perfect graphs are, for instance, precisely those
    graphs $G$ where the stable set polytope STAB($G$) equals the
    fractional stable set polytope QSTAB($G$). The dilation ratio ${\text
    {min}}\{t : {\text {QSTAB}}(G) \subseteq t \,\,{\text {STAB}}(G)\}$ of
    the two polytopes yields the imperfection ratio of $G$. It is NP-hard
    to compute and, for most graph classes, it is even unknown whether it
    is bounded. For graphs $G$ such that all facets of STAB($G$) are rank
    constraints associated with antiwebs, we characterize the imperfection
    ratio and bound it by 3/2. Outgoing from this result, we characterize
    and bound the imperfection ratio for several graph classes, including
    near-bipartite graphs and their complements, namely quasi-line graphs,
    by means of induced antiwebs and webs, respectively.
rv: