Comparing Imperfection Ratio and Imperfection Index for Graph Classes

Issue		RAIRO Oper. Res. Volume 42, Number 4, October-December 2008 ALIO/EURO V Conference on Combinatorial Optimization


Page(s)		485 - 500
DOI		10.1051/ro:2008030
Published online		04 April 2009

RAIRO-Oper. Res. 42 (2008) 485-500
DOI: 10.1051/ro:2008030

Comparing Imperfection Ratio and Imperfection Index for Graph Classes

Arie M.C.A. Koster¹ and Annegret K. Wagler²

¹ University of Warwick, Centre for Discrete Mathematics and its Applications (DIMAP), Coventry CV4 7AL, UK; Arie.Koster@wbs.ac.uk - Supported by the DFG research group “Algorithms, Structure, Randomness” (Grant number GR 883/9-3, GR 883/9-4).
² Otto-von-Guericke-Universität Magdeburg, Fakultät für Mathematik, Institut für Mathematische Optimierung (IMO), Universitätsplatz 2, 39106 Magdeburg, Germany; wagler@imo.math.uni-magdeburg.de

Received May 24, 2007. Accepted January 09, 2008 Published online 4 April 2009

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.

Mathematics Subject Classification. 05C17, 90C57.

Key words: Perfect graphs, imperfection ratio, imperfection index.

© EDP Sciences, ROADEF, SMAI 2008

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.