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.
|Title of host publication||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Subtitle of host publication||21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020; London; United Kingdom; 8 June 2020 through 10 June 2020|
|Editors||Daniel Bienstock, Giacomo Zambelli|
|Place of Publication||Cham Switzerland|
|Number of pages||13|
|Publication status||Published - 14 Apr 2020|
|Event||International Conference on Integer Programming and Combinatorial Optimization, 2020 - Online, London, United Kingdom|
Duration: 8 Jun 2020 → 10 Jun 2020
Conference number: 21st
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||International Conference on Integer Programming and Combinatorial Optimization, 2020|
|Abbreviated title||IPCO 2020|
|Period||8/06/20 → 10/06/20|
|Other||The 21st Conference on Integer Programming and Combinatorial Optimization (IPCO XXI) took place online on June 8-10. The conference was preceded by an online Summer School on June 6-7. The conference and summer school were organised by the Department of Mathematics at the London School of Economics.|
IPCO conference is under the auspices of the Mathematical Optimization Society. It is held every year. The conference is a forum for researchers and practitioners working on various aspects of integer programming and combinatorial optimization. The aim is to present recent developments in theory, computation, and applications in these areas.