Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-30T23:48:25.785Z Has data issue: false hasContentIssue false
  • English
  • Français

Comparing Imperfection Ratio and Imperfection Index for Graph Classes

Published online by Cambridge University Press:  04 April 2009

Arie M.C.A. Koster  and
Annegret K. Wagler
Arie M.C.A. Koster
Affiliation:
University of Warwick, Centre for Discrete Mathematics and its Applications (DIMAP), Coventry CV4 7AL, UK; [email protected] - Supported by the DFG research group “Algorithms, Structure, Randomness” (Grant number GR 883/9-3, GR 883/9-4).
Annegret K. Wagler
Affiliation:
Otto-von-Guericke-Universität Magdeburg, Fakultät für Mathematik, Institut für Mathematische Optimierung (IMO), Universitätsplatz 2, 39106 Magdeburg, Germany; [email protected]
Get access

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 STAB(G) coincides with the fractional stable set polytope QSTAB(G). For all imperfect graphs G it holds that STAB(G) ⊂ 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 graphclasses [7,12].
Outgoing from a graph-theoretical interpretation of the imperfectionindex, we prove that there exists no upper bound on the imperfection indexfor those graph classes with a known bounded imperfection ratio.Comparing the two invariants on those classes, it seems that theimperfection index measures imperfection much more roughly than theimperfection ratio; we, therefore, discuss possible directions forrefinements.

Keywords

Perfect graphsimperfection ratioimperfection index.
Type
Research Article
Information
RAIRO - Operations Research , Volume 42 , Issue 4: ALIO/EURO V Conference on Combinatorial Optimization , October 2008 , pp. 485 - 500
Copyright
© EDP Sciences, ROADEF, SMAI, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aguilera, N.E., Escalante, M.S., and Nasini, G.L., A generalization of the Perfect Graph Theorem under the disjunctive index. Math. Oper. Res. 27 (2002) 460–469.
Balas, E., Cornuéjols, G., and Ceria, S., A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Program. 58 (1993) 295–324. CrossRef
Bland, R.G., Huang, H.-C., and Trotter, L.E., Graphical Properties Related, Jr. to Minimal Imperfection. Discrete Math. 27 (1979) 11–22. CrossRef
Ceria, S., Lift-and-project cuts and perfect graphs. Math. Program. 98 (2003) 309–317. CrossRef
Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R., The Strong Perfect Graph Theorem. Ann. Math. 164 (2006) 51–229. CrossRef
Chvátal, V., Certain Polytopes Associated, On with Graphs. J. Comb. Theory (B) 18 (1975) 138–154. CrossRef
S. Coulonges, A. Pêcher, and A. Wagler, Characterizing and bounding the imperfection ratio for some graph classes. Math. Program. (to appear).
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.
Edmonds, J.R., Maximum Matching and a Polyhedron with (0, 1) Vertices. J. Res. Nat. Bur. Standards 69B (1965) 125–130. CrossRef
Gerards, A.M.H. and Schrijver, A., Matrices with the Edmonds-Johnson Property. Combinatorica 6 (1986) 403–417. CrossRef
Gerards, A.M.H., Maróti, G., and Schrijver, A., 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.
Gerke, S. and McDiarmid, C., Graph imperfection I, II. J. Comb. Theor. (B) 83 (2001) 58–78, 79–101. CrossRef
M. Grötschel, L. Lovász, and A. Schrijver, Geometric algorithms and combinatorial optimization. Springer-Verlag (1988).
Larsen, M., Propp, J., and Ullman, D.H., The fractional chromatic number of Mycielski graphs. J. Graph Theory 20 (1995) 411–416. CrossRef
Lipták, L. and Tunçel, L., Lift-and-project ranks and antiblocker duality. Oper. Res. Lett. 33 (2005) 35–41.
Lovász, L., Normal hypergraphs and the weak perfect graph conjecture. Discrete Math. 2 (1972) 253–267. CrossRef
Mycielski, J., Sur le coloriage des graphs. Colloq. Math. 3 (1955) 161–162. CrossRef
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.
B. Reed and J. Ramirez-Alfonsin, Perfect Graphs, Wiley (2001).
Shepherd, F.B., Near-Perfect Matrices. Math. Program. 64 (1994) 295–323. CrossRef
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).
Wagler, A., Antiwebs are rank-perfect. A Quaterly Journal of Operations Research 2 (2004) 149–152.
Wagler, A., On the stable set polytopes of classes of near-bipartite graphs. A Quaterly Journal of Operations Research 3 (2005) 329–336.