TY - GEN
T1 - The stable set problem in graphs with bounded genus and bounded odd cycle packing number
AU - Conforti, Michele
AU - Fiorini, Samuel
AU - Huynh, Tony
AU - Joret, Gwenaël
AU - Weltge, Stefan
N1 - Publisher Copyright:
Copyright © 2020 by SIAM
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85084068181&partnerID=8YFLogxK
U2 - 10.1137/1.9781611975994.176
DO - 10.1137/1.9781611975994.176
M3 - Conference contribution
AN - SCOPUS:85084068181
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 2896
EP - 2915
BT - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
A2 - Chawla, Shuchi
PB - Association for Computing Machinery
T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
Y2 - 5 January 2020 through 8 January 2020
ER -