# Comparing Imperfection Ratio and Imperfection Index for Graph Classes

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

RAIRO - Operations Research (2009)

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

## Access Full Article

top## Abstract

top## How to cite

topKoster, Arie M.C.A., and Wagler, Annegret K.. "Comparing Imperfection Ratio and Imperfection Index for Graph Classes." RAIRO - Operations Research 42.4 (2009): 485-500. <http://eudml.org/doc/105416>.

@article{Koster2009,

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 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},

keywords = {Perfect graphs; imperfection ratio; imperfection index.; perfect graphs; imperfection index},

language = {eng},

month = {4},

number = {4},

pages = {485-500},

publisher = {EDP Sciences},

title = {Comparing Imperfection Ratio and Imperfection Index for Graph Classes},

url = {http://eudml.org/doc/105416},

volume = {42},

year = {2009},

}

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

DA - 2009/4//

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 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 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.; perfect graphs; imperfection index

UR - http://eudml.org/doc/105416

ER -

## References

top- 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.
- 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.
- R.G. Bland, H.-C. Huang, and L.E. Trotter, Jr., Graphical Properties Related to Minimal Imperfection. Discrete Math.27 (1979) 11–22.
- S. Ceria, Lift-and-project cuts and perfect graphs. Math. Program.98 (2003) 309–317.
- M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The Strong Perfect Graph Theorem. Ann. Math.164 (2006) 51–229.
- V. Chvátal, On Certain Polytopes Associated with Graphs. J. Comb. Theory (B)18 (1975) 138–154.
- 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.
- J.R. Edmonds, Maximum Matching and a Polyhedron with (0, 1) Vertices. J. Res. Nat. Bur. Standards69B (1965) 125–130.
- A.M.H. Gerards and A. Schrijver, Matrices with the Edmonds-Johnson Property. Combinatorica6 (1986) 403–417.
- 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.
- S. Gerke and C. McDiarmid, Graph imperfection I, II. J. Comb. Theor. (B)83 (2001) 58–78, 79–101.
- M. Grötschel, L. Lovász, and A. Schrijver, Geometric algorithms and combinatorial optimization. Springer-Verlag (1988).
- M. Larsen, J. Propp, and D.H. Ullman, The fractional chromatic number of Mycielski graphs. J. Graph Theory20 (1995) 411–416.
- L. Lipták and L. Tunçel, Lift-and-project ranks and antiblocker duality. Oper. Res. Lett.33 (2005) 35–41.
- L. Lovász, Normal hypergraphs and the weak perfect graph conjecture. Discrete Math.2 (1972) 253–267.
- J. Mycielski, Sur le coloriage des graphs. Colloq. Math.3 (1955) 161–162.
- 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).
- F.B. Shepherd, Near-Perfect Matrices. Math. Program.64 (1994) 295–323.
- 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 Optimization4 (2004).
- A. Wagler, Antiwebs are rank-perfect. A Quaterly Journal of Operations Research2 (2004) 149–152.
- A. Wagler, On the stable set polytopes of classes of near-bipartite graphs. A Quaterly Journal of Operations Research3 (2005) 329–336.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.