The stable set problem in graphs with bounded genus and bounded odd cycle packing number

Michele Conforti, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Stefan Weltge

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

17 Scopus citations

Abstract

Consider the family of graphs without k node-disjoint odd cycles, where k is a constant. Determining the complexity of the stable set problem for such graphs G is a long-standing problem. We give a polynomial-time algorithm for the case that G can be further embedded in a (possibly nonorientable) surface of bounded genus. Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes. To this end, we show that 2-sided odd cycles satisfy the Erdos-Pósa property in graphs embedded in a fixed surface. This extends the fact that odd cycles satisfy the Erdos-Pósa property in graphs embedded in a fixed orientable surface (Kawarabayashi & Nakamoto, 2007). Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class, which turns out to be efficiently solvable in our case.

Original languageEnglish
Title of host publication31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
EditorsShuchi Chawla
PublisherAssociation for Computing Machinery
Pages2896-2915
Number of pages20
ISBN (Electronic)9781611975994
DOIs
StatePublished - 2020
Event31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States
Duration: 5 Jan 20208 Jan 2020

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2020-January
ISSN (Print)1071-9040
ISSN (Electronic)1557-9468

Conference

Conference31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
Country/TerritoryUnited States
CitySalt Lake City
Period5/01/208/01/20

Fingerprint

Dive into the research topics of 'The stable set problem in graphs with bounded genus and bounded odd cycle packing number'. Together they form a unique fingerprint.

Cite this