
Discrete Mathematics and Optimization Seminar

Nov. 26, 2008 MC 320, 4:00PM
A new algorithm for the maximum weighted stable set problem on clawfree graphs
Gianpaolo Oriolo
Universita' di Tor Vergata

The stable set (SS) problem on clawfree graph is a fundamental generalization of the matching problem. E.g. it was observed by Berge in 1970 that the augmenting path theorem extends to SS in clawfree graphs.
Yet, the only polynomialtime algorithm for the maximum weighted SS problem on clawfree graphs was given by Minty and dates back to 1980. The algorithm (revised by Nakamura and Tamura in 2001), is somewhat involved and requires the solution of O(n^3) matching problems in auxiliary graphs. A different version of Minty's algorithm was given by Schrijver in 2005.
On the other hand, very elegant algorithms were given by: Lovasz and Plummer, for the unweighted SS problem on clawfree graph (based on graph reductions); Pulleyblank and Shepherd for the weighted SS problem on distance clawfree graphs (a subclass of clawfree graphs).
In this talk, we present a new polynomialtime algorithm for the weighted SS problem on clawfree graphs. This algorithm is based on on graph reductions and a new decomposition theorem, inspired by some recent results of Chudnovsky and Seymour. First we decompose the graph into o(n) simpler graphs that are distance clawfree, then evaluate a maximum weighted SS by solving a single matching problem.
Joint work with:
Ugo Pietropaoli, Universita' di Tor Vergata
Gautier Stauffer, IBM Zurich



