Comparing imperfection ratio and imperfection index for graph classes

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

RAIRO - Operations Research - Recherche Opérationnelle (2008)

  • Volume: 42, Issue: 4, page 485-500
  • ISSN: 0399-0559

Abstract

top
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 where the stable set polytope coincides with the fractional stable set polytope . For all imperfect graphs it holds that . 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 , the disjunctive index of , and the dilation ratio of the two polytopes. Including only certain types of facets for , 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 and , whereas Aguilera et al. [1] suggest to take the disjunctive index of as the imperfection index of . 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.

How to cite

top

Koster, Arie M. C. A., and Wagler, Annegret K.. "Comparing imperfection ratio and imperfection index for graph classes." RAIRO - Operations Research - Recherche Opérationnelle 42.4 (2008): 485-500. <http://eudml.org/doc/246020>.

@article{Koster2008,
abstract = {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 $\{\rm STAB\}(G)$ coincides with the fractional stable set polytope $\{\rm QSTAB\}(G)$. For all imperfect graphs $G$ it holds that $\{\rm STAB\}(G) \subset \{\rm 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 $\{\rm STAB\}(G)$, the disjunctive index of $\{\rm QSTAB\}(G)$, and the dilation ratio of the two polytopes. Including only certain types of facets for $\{\rm 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 $\{\rm STAB\}(G)$ and $\{\rm QSTAB\}(G)$, whereas Aguilera et al. [1] suggest to take the disjunctive index of $\{\rm 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.},
author = {Koster, Arie M. C. A., Wagler, Annegret K.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {perfect graphs; imperfection ratio; imperfection index},
language = {eng},
number = {4},
pages = {485-500},
publisher = {EDP-Sciences},
title = {Comparing imperfection ratio and imperfection index for graph classes},
url = {http://eudml.org/doc/246020},
volume = {42},
year = {2008},
}

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
PB - EDP-Sciences
VL - 42
IS - 4
SP - 485
EP - 500
AB - 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 ${\rm STAB}(G)$ coincides with the fractional stable set polytope ${\rm QSTAB}(G)$. For all imperfect graphs $G$ it holds that ${\rm STAB}(G) \subset {\rm 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 ${\rm STAB}(G)$, the disjunctive index of ${\rm QSTAB}(G)$, and the dilation ratio of the two polytopes. Including only certain types of facets for ${\rm 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 ${\rm STAB}(G)$ and ${\rm QSTAB}(G)$, whereas Aguilera et al. [1] suggest to take the disjunctive index of ${\rm 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.
LA - eng
KW - perfect graphs; imperfection ratio; imperfection index
UR - http://eudml.org/doc/246020
ER -

References

top
  1. [1] N.E. Aguilera, M.S. Escalante, and G.L. Nasini, A generalization of the Perfect Graph Theorem under the disjunctive index. Math. Oper. Res. 27 (2002) 460–469. Zbl1083.05505MR1926653
  2. [2] E. Balas, G. Cornuéjols, and S. Ceria, A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Program. 58 (1993) 295–324. Zbl0796.90041MR1216789
  3. [3] R.G. Bland, H.-C. Huang, and L.E. Trotter, Jr., Graphical Properties Related to Minimal Imperfection. Discrete Math. 27 (1979) 11–22. Zbl0421.05028MR534949
  4. [4] S. Ceria, Lift-and-project cuts and perfect graphs. Math. Program. 98 (2003) 309–317. Zbl1082.05044MR2021058
  5. [5] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The Strong Perfect Graph Theorem. Ann. Math. 164 (2006) 51–229. Zbl1112.05042MR2233847
  6. [6] V. Chvátal, On Certain Polytopes Associated with Graphs. J. Comb. Theory (B) 18 (1975) 138–154. Zbl0277.05139MR371732
  7. [7] S. Coulonges, A. Pêcher, and A. Wagler, Characterizing and bounding the imperfection ratio for some graph classes. Math. Program. (to appear). Zbl1169.90025MR2470884
  8. [8] W.H. Cunningham, Polyhedra for composed independence systems, in: Bonn Workshop on Combinatorial Optimization, edited by A. Bachem, M. Grötschel, and B. Korte, Ann. Discrete Math. 16 (1982) 57–67. Zbl0493.05015MR686299
  9. [9] J.R. Edmonds, Maximum Matching and a Polyhedron with (0, 1) Vertices. J. Res. Nat. Bur. Standards 69B (1965) 125–130. Zbl0141.21802MR183532
  10. [10] A.M.H. Gerards and A. Schrijver, Matrices with the Edmonds-Johnson Property. Combinatorica 6 (1986) 403–417. Zbl0641.05039MR879340
  11. [11] A.M.H. Gerards, G. Maróti, and A. Schrijver, Note on: N.E. Aguilera, M.S. Escalante, and G.L. Nasini, “A generalization of the Perfect Graph Theorem under the disjunctive index”. Math. Oper. Res. 28 (2003) 884–885. Zbl1082.05504MR2015917
  12. [12] S. Gerke and C. McDiarmid, Graph imperfection I, II. J. Comb. Theor. (B) 83 (2001) 58–78, 79–101. Zbl1018.05027MR1855796
  13. [13] M. Grötschel, L. Lovász, and A. Schrijver, Geometric algorithms and combinatorial optimization. Springer-Verlag (1988). Zbl0634.05001MR936633
  14. [14] M. Larsen, J. Propp, and D.H. Ullman, The fractional chromatic number of Mycielski graphs. J. Graph Theory 20 (1995) 411–416. Zbl0830.05027
  15. [15] L. Lipták and L. Tunçel, Lift-and-project ranks and antiblocker duality. Oper. Res. Lett. 33 (2005) 35–41. Zbl1076.90035MR2091033
  16. [16] L. Lovász, Normal hypergraphs and the weak perfect graph conjecture. Discrete Math. 2 (1972) 253–267. Zbl0239.05111MR302480
  17. [17] J. Mycielski, Sur le coloriage des graphs. Colloq. Math. 3 (1955) 161–162. Zbl0064.17805MR69494
  18. [18] G.L. Nasini, El índice de imperfección de un grafo y su complemento, in Anales de las XXX JAIIO-SIO’01 (2001) 101–106. 
  19. [19] B. Reed and J. Ramirez-Alfonsin, Perfect Graphs, Wiley (2001). Zbl0972.00015MR1858793
  20. [20] F.B. Shepherd, Near-Perfect Matrices. Math. Program. 64 (1994) 295–323. Zbl0804.05036MR1286452
  21. [21] A. Wagler, Relaxing perfectness: which graphs are “almost” perfect? in The sharpest cut, impact of Manfred Padberg and his Work, edited by M. Grötschel , MPS/SIAM series on Optimization 4 (2004). Zbl1072.05026MR2077556
  22. [22] A. Wagler, Antiwebs are rank-perfect. A Quaterly Journal of Operations Research 2 (2004) 149–152. Zbl1112.05082MR2073117
  23. [23] A. Wagler, On the stable set polytopes of classes of near-bipartite graphs. A Quaterly Journal of Operations Research 3 (2005) 329–336. Zbl1134.90551

NotesEmbed ?

top

You must be logged in to post comments.