|
|
Discrete Mathematics and Optimization Seminar
|
Nov. 26, 2008
MC 320, 4:00PM
|
A new algorithm for the maximum weighted stable set problem on claw-free graphs
Gianpaolo Oriolo
Universita' di Tor Vergata
|
The stable set (SS) problem on claw-free 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 claw-free graphs.
Yet, the only polynomial-time algorithm for the maximum weighted SS problem on claw-free 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 claw-free graph (based on graph reductions); Pulleyblank and Shepherd for the weighted SS problem on distance claw-free graphs (a subclass of claw-free graphs).
In this talk, we present a new polynomial-time algorithm for the weighted SS problem on claw-free 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 claw-free, 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
|
|
|
|