Split cuts and the stable set polytope of quasi-line graphs

Tuesday, July 26, 2005 - 10:15am - 11:00am
EE/CS 3-180
Friedrich Eisenbrand (Max-Planck-Institut für Informatik)
Edmonds showed in 1965 that the convex hull of all matchings of a
graph can be obtained by applying one round of Gomory-Chv'atal cutting
planes to the fractional matching polytope. More precisely, he showed
that this convex hull can be described by non-negativity, degree and
odd-set constraints.

15 years later, Minty and Sbihi showed that a
maximum-cardinality stable set in a claw-free graph can be computed in
polynomial time, thereby generalizing Edmonds' algorithm for maximum
cardinality matching. Since then, it is a long standing open problem
to find an explicit description of the stable set polytope of
claw-free graphs.

In this talk we show that the convex hull of stable sets of quasi-line
graphs is obtainable by applying one round of split cuts. The class
of quasi-line graphs is a proper superclass of line graphs and a
proper subclass of claw-free graphs for which it is known that not all
facets have 0/1 normal vectors. The necessary split-cuts are a
generalization of Edmonds' odd-set inequalities, called clique family

Joint work with G. Oriolo, P. Ventura and G. Stauffer.