## arXiv Analytics

### arXiv:1908.06300 [cs.DM]AbstractReferencesReviewsResources

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

Published 2019-08-17Version 1

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 non-orientable) 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 Erd\H{o}s-P\'osa property in graphs embedded in a fixed surface. This extends the fact that odd cycles satisfy the Erd\H{o}s-P\'osa 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.

Categories: cs.DM, cs.DS, math.CO, math.OC
Related articles: Most relevant | Search more
arXiv:1911.01478 [cs.DM] (Published 2019-11-04)
Persistency of Linear Programming Formulations for the Stable Set Problem
arXiv:1004.4484 [cs.DM] (Published 2010-04-26)
Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus
arXiv:1911.10912 [cs.DM] (Published 2019-11-25)
Minimum-cost integer circulations in given homology classes