Characterizing and bounding the imperfection ratio for some classes of graphs
成果类型：
Article
署名作者：
Coulonges, Sylvain; Pecher, Arnaud; Wagler, Annegret K.
署名单位：
Otto von Guericke University; Universite de Bordeaux; Centre National de la Recherche Scientifique (CNRS)
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-007-0182-9
发表日期：
2009
页码：
37-46
关键词：
摘要：
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 min{t : QSTAB(G) subset of t 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.