Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs

In this paper, we provide the first linear programming formulations for the stable set problem in claw-free graphs, together with polynomial time separation routines for those formulations (they are not compact). We then exploit one of those extended formulations and propose a new polytime algorithm for solving the separation problem for the stable set polytope of claw-free graphs. This routine combines a separation algorithm for the matching polytope due to Padberg and Rao and the solution of (moderate size) compact linear programs. Hence, it does not rely on the ellipsoid method and seems to be appropriate to be inserted in branch and cut frameworks for solving real world problems.

Published in:
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, null, null, 1298-1308
Presented at:
2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)

 Record created 2012-10-25, last modified 2018-01-28

Rate this document:

Rate this document:
(Not yet reviewed)