Friday, May 21, 2010
3:30 pm, MC 5158

Yuri Faenza
Università di Roma "Tor Vergata"

The matching structure behind the composition of strips

A strip is a triple (G,a,b), where G is a simple, undirected graph and a,b are vertices of G whose neighborhood is a clique. The composition of strips takes as input a set of strips, and outputs a graph. Chudnovsky and Seymour showed that strips from a suitable family form the building blocks of a wide class of claw-free graphs, meaning that every graph in this class can be expressed as the composition of strips from the family, and conversely a composition of those strips always produces a claw-free graph from this class. One of the reasons why claw-free graphs attracted the interest of many researchers is that they generalize line graphs, thus the Maximum (Weighted) Stable Set problem on claw-free graphs generalizes the maximum (weighted) matching problem.
In this talk we show that, in fact, MWSS problems on graphs that are the composition of strips share a common matching-like structure, both from an algorithmic and from a polyhedral point of view. We also address a number of applications of these results, mainly back in the context of claw-free graphs, including extended formulations and a polytime separation routine for the stable set polytope of claw-free graphs, and a new combinatorial algorithm for the MWSS on claw-free graphs. These latter results use a novel algorithmic decomposition theorem for claw-free graphs with stability number at least 4.

These results are part of the speaker's Ph.D. thesis, and are a joint work with G.Oriolo and G. Stauffer.