Comparing imperfection ratio and imperfection index for graph classes

Koster, Arie M. C. A.; Wagler, Annegret K.

doi:10.1051/ro:2008030

Geodesic

Parcourir par

Comparing imperfection ratio and imperfection index for graph classes

Koster, Arie M. C. A. ; Wagler, Annegret K.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 4, pp. 485-500

Voir la notice de l'article provenant de la source Numdam

Résumé

Perfect graphs constitute a well-studied graph class with a rich structure, 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)$ coincides with the fractional stable set polytope $QSTAB (G)$ . For all imperfect graphs $G$ it holds that $STAB (G) \subset QSTAB (G)$ . It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect. We discuss three different concepts, involving the facet set of $STAB (G)$ , the disjunctive index of $QSTAB (G)$ , and the dilation ratio of the two polytopes. Including only certain types of facets for $STAB (G)$ , we obtain graphs that are in some sense close to perfect graphs, for example minimally imperfect graphs, and certain other classes of so-called rank-perfect graphs. The imperfection ratio has been introduced by Gerke and McDiarmid [12] as the dilation ratio of $STAB (G)$ and $QSTAB (G)$ , whereas Aguilera et al. [1] suggest to take the disjunctive index of $QSTAB (G)$ as the imperfection index of $G$ . For both invariants there exist no general upper bounds, but there are bounds known for the imperfection ratio of several graph classes [7,12]. Outgoing from a graph-theoretical interpretation of the imperfection index, we prove that there exists no upper bound on the imperfection index for those graph classes with a known bounded imperfection ratio. Comparing the two invariants on those classes, it seems that the imperfection index measures imperfection much more roughly than the imperfection ratio; we, therefore, discuss possible directions for refinements.

DOI : 10.1051/ro:2008030

Classification : 05C17, 90C57
Keywords: perfect graphs, imperfection ratio, imperfection index

@article{RO_2008__42_4_485_0,
     author = {Koster, Arie M. C. A. and Wagler, Annegret K.},
     title = {Comparing imperfection ratio and imperfection index for graph classes},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {485--500},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {4},
     year = {2008},
     doi = {10.1051/ro:2008030},
     mrnumber = {2469108},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2008030/}
}

TY  - JOUR
AU  - Koster, Arie M. C. A.
AU  - Wagler, Annegret K.
TI  - Comparing imperfection ratio and imperfection index for graph classes
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2008
SP  - 485
EP  - 500
VL  - 42
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro:2008030/
DO  - 10.1051/ro:2008030
LA  - en
ID  - RO_2008__42_4_485_0
ER  -

%0 Journal Article
%A Koster, Arie M. C. A.
%A Wagler, Annegret K.
%T Comparing imperfection ratio and imperfection index for graph classes
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2008
%P 485-500
%V 42
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro:2008030/
%R 10.1051/ro:2008030
%G en
%F RO_2008__42_4_485_0

Koster, Arie M. C. A.; Wagler, Annegret K. Comparing imperfection ratio and imperfection index for graph classes. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 4, pp. 485-500. doi: 10.1051/ro:2008030

Cité par Sources :