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

Michele Conforti; Samuel Fiorini; Tony Huynh; Stefan Weltge

doi:10.1007/978-3-030-45771-6_9

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

Michele Conforti, Samuel Fiorini, Tony Huynh, Stefan Weltge

Associate Professorship of Discrete Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

10 Scopus citations

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 language	English
Title of host publication	Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings
Editors	Daniel Bienstock, Giacomo Zambelli
Publisher	Springer
Pages	104-116
Number of pages	13
ISBN (Print)	9783030457709
DOIs	https://doi.org/10.1007/978-3-030-45771-6_9
State	Published - 2020
Event	21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020 - London, United Kingdom Duration: 8 Jun 2020 → 10 Jun 2020

Publication series

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

Conference

Conference	21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020
Country/Territory	United Kingdom
City	London
Period	8/06/20 → 10/06/20

Access to Document

10.1007/978-3-030-45771-6_9

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.), Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings (pp. 104-116). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12125 LNCS). Springer. https://doi.org/10.1007/978-3-030-45771-6_9

Conforti, Michele ; Fiorini, Samuel ; Huynh, Tony et al. / Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles. Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings. editor / Daniel Bienstock ; Giacomo Zambelli. Springer, 2020. pp. 104-116 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{10e6c9665bdf463baa6c28aa7bde3e67,

title = "Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles",

abstract = "Let G be an n-node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC{\textquoteright}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.",

author = "Michele Conforti and Samuel Fiorini and Tony Huynh and Stefan Weltge",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020 ; Conference date: 08-06-2020 Through 10-06-2020",

year = "2020",

doi = "10.1007/978-3-030-45771-6_9",

language = "English",

isbn = "9783030457709",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "104--116",

editor = "Daniel Bienstock and Giacomo Zambelli",

booktitle = "Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings",

}

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), Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12125 LNCS, Springer, pp. 104-116, 21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020, London, United Kingdom, 8/06/20. https://doi.org/10.1007/978-3-030-45771-6_9

Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles. / Conforti, Michele; Fiorini, Samuel; Huynh, Tony et al.
Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings. ed. / Daniel Bienstock; Giacomo Zambelli. Springer, 2020. p. 104-116 (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 proceeding › Conference contribution › peer-review

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

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 -

Conforti M, Fiorini S, Huynh T, Weltge S. Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles. In Bienstock D, Zambelli G, editors, Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings. Springer. 2020. p. 104-116. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-45771-6_9

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this