TY - GEN
T1 - Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
AU - Conforti, Michele
AU - Fiorini, Samuel
AU - Huynh, Tony
AU - Weltge, Stefan
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - 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-[Formula Presented] extended formulation for the stable set polytope of G.
AB - 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-[Formula Presented] extended formulation for the stable set polytope of G.
UR - http://www.scopus.com/inward/record.url?scp=85083981408&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-45771-6_9
DO - 10.1007/978-3-030-45771-6_9
M3 - Conference contribution
AN - SCOPUS:85083981408
SN - 9783030457709
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 104
EP - 116
BT - Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings
A2 - Bienstock, Daniel
A2 - Zambelli, Giacomo
PB - Springer
T2 - 21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020
Y2 - 8 June 2020 through 10 June 2020
ER -