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" [...]


  The majority of financial loan companies provide the service of getting North Carolina Loans Online for U.S. citizens. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.