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.
, , ,
Mathematical Programming Series B
Networks and Optimization

Conforti, M., Gerards, B., & 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