Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
2020
Let G be an n-node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC’17) for bimodular integer programs can be used to find a maximum weight stable set in G in strongly polynomial time. Building on structural results characterizing sufficiently connected graphs without two disjoint odd cycles, we construct a size-\(O(n^2)\) extended formulation for the stable set polytope of G.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
13
References
8
Citations
NaN
KQI