We develop decomposition/composition tools for efficiently solving maximum weight stable sets problems as well as for describing them as polynomially sized linear programs (using "compact systems"). Some of these are well-known but need some extra work to yield polynomial "decomposition schemes".
We apply the tools to graphs with no even hole and no cap. A hole is a chordless cycle of length greater than three and a cap is a hole together with an additional node that is adjacent to two adjacent nodes of the hole and that has no other neighbors on the hole.
Additional Metadata
Keywords stable sets, decomposition, algorithms, extended formulations
MSC Combinatorial optimization (msc 90C27)
THEME Logistics (theme 3)
Publisher Springer
Persistent URL dx.doi.org/10.1007/s10107-015-0912-3
Journal Mathematical Programming Series B
Note Published online 2015-06-02
Conforti, M, Gerards, A.M.H, & Pashkovich, K. (2015). Stable sets and graphs with no even holes. Mathematical Programming Series B, 153, 13–39. doi:10.1007/s10107-015-0912-3