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 PaperResearch

1 Citation (Scopus)

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 publicationProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Subtitle of host publication31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020; Salt Lake City; United States; 5 January 2020 through 8 January 2020
EditorsShuchi Chawla
Place of PublicationUSA
PublisherAssociation for Computing Machinery (ACM)
Pages2896-2915
Number of pages20
ISBN (Electronic)9781611975994
Publication statusPublished - 1 Jan 2020
Externally publishedYes
EventAnnual ACM-SIAM Symposium on Discrete Algorithms, 2020 - Hilton Salt Lake City Center, Salt Lake City, United States of America
Duration: 5 Jan 20208 Jan 2020
Conference number: 31st
https://www.siam.org/conferences/cm/conference/soda20

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2020-January

Conference

ConferenceAnnual ACM-SIAM Symposium on Discrete Algorithms, 2020
Abbreviated titleSODA20
CountryUnited States of America
CitySalt Lake City
Period5/01/208/01/20
OtherThis symposium focuses on research topics related to efficient algorithms and
data structures for discrete problems. In addition to the design of such methods
and structures, the scope also includes their use, performance analysis, and the
mathematical problems related to their development or limitations. Performance
analyses may be analytical or experimental and may address worst-case or
expected-case performance. Studies can be theoretical or based on data sets that
have arisen in practice and may address methodological issues involved in
performance analysis.
Internet address

Cite this