Extended formulations for stable set polytopes of graphs without two disjoint odd cycles

Michele Conforti, Samuel Fiorini, Tony Huynh, Stefan Weltge

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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(n2) extended formulation for the stable set polytope of G.

Original languageEnglish
Number of pages20
JournalMathematical Programming
DOIs
Publication statusAccepted/In press - 2021
  • Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles

    Conforti, M., Fiorini, S., Huynh, T. & Weltge, S., 14 Apr 2020, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): 21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020; London; United Kingdom; 8 June 2020 through 10 June 2020. Bienstock, D. & Zambelli, G. (eds.). Cham Switzerland: Springer-Praxis, Vol. 12125. p. 104-116 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12125 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference PaperOther

    3 Citations (Scopus)

Cite this