Stability critical graphs and ranks facets of the stable set polytope

✍ Scribed by E.C. Sewell; L.E. Trotter Jr.

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 616 KB
• Volume: 147
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00168-i

✦ Synopsis

Rank inequalities due to stability critical (u-critical) graphs are used to develop a finite nested sequence of linear relaxations of the stable set polytope, the strongest of which provides an integral max-min relation: In a simple graph, the maximum size of a stable set is equal to the minimum (weighted) value of a cover of nodes by or-critical subgraphs. For a simple graph containing no even subdivision of K,, these results imply that every rank facet is due either to an edge or to an odd cycle; consequently, the max-min relation specializes to give that the cardinality of a largest stable set equals the minimum value of a node covering by edges and odd cycles. This leads to a polynomial-time algorithm to find a maximum stable set and a minimum valued cover of nodes by edges and odd cycles in such a graph.