Friday, 11:00 - 11:25 h, Room: H 3008


Yuri Faenza
Separating stable sets in claw-free graphs through extended formulations

Coauthors: Gianpaolo Oriolo, Gautier Stauffer


The stable set polytope in claw-free graphs (ssp-cf) is a well-known generalization of the matching polytope. A linear description of the latter only requires rank inequalities (i.e., with 0/1 coefficients), while the associated separation problem can be solved via a purely combinatorial routine. For ssp-cf the situation is quite different: no complete description is known, and there exist examples of facets with arbitrarily high coefficients. Moreover, the only known separation routine relies on the ellipsoid method.
In this talk, we provide linear programming extended formulations for ssp-cf, together with polynomial time separation routines for those formulations (they are not compact). Those formulations rely on combinatorial optimization, polyhedral combinatorics, and structural graph theory results. We then exploit one of those extended formulations to propose a new polytime algorithm for solving the separation problem for ssp-cf. This routine combines the separation algorithm for the matching polytope and the solution of (moderate size) compact linear programs, hence it does not require the application of the ellipsoid method.


Talk 2 of the invited session Fri.1.H 3008
"Algorithms in claw-free graphs" [...]
Cluster 2
"Combinatorial optimization" [...]


  Getting California Loans Online should be thought of many times. Moreover, to order Cialis Daily online is highly advantageous because it interacts well with the small portions of alcohol and food.