Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles

Michele Conforti, Samuel Fiorini, Tony Huynh, Stefan Weltge

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

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-[Formula Presented] extended formulation for the stable set polytope of G.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Subtitle of host publication21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020; London; United Kingdom; 8 June 2020 through 10 June 2020
EditorsDaniel Bienstock, Giacomo Zambelli
Place of PublicationCham Switzerland
PublisherSpringer-Praxis
Pages104-116
Number of pages13
Volume12125
ISBN (Electronic)978-3-030-45771-6
ISBN (Print)9783030457709
DOIs
Publication statusPublished - 14 Apr 2020
EventInternational Conference on Integer Programming and Combinatorial Optimization, 2020 - Online, London, United Kingdom
Duration: 8 Jun 202010 Jun 2020
Conference number: 21st
https://www.lse.ac.uk/IPCO-2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12125 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Integer Programming and Combinatorial Optimization, 2020
Abbreviated titleIPCO 2020
CountryUnited Kingdom
CityLondon
Period8/06/2010/06/20
OtherThe 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.
Internet address

Cite this

Conforti, M., Fiorini, S., Huynh, T., & Weltge, S. (2020). Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles. In D. Bienstock, & G. Zambelli (Eds.), 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 (Vol. 12125, pp. 104-116). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12125 LNCS). Springer-Praxis. https://doi.org/10.1007/978-3-030-45771-6_9