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.
stable sets, decomposition, algorithms, extended formulations
Combinatorial optimization (msc 90C27)
Logistics (theme 3)
Mathematical Programming Series B
Published online 2015-06-02
Networks and Optimization

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