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 language | English |
|---|---|
| Title of host publication | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
| Subtitle of host publication | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020; Salt Lake City; United States; 5 January 2020 through 8 January 2020 |
| Editors | Shuchi Chawla |
| Place of Publication | USA |
| Publisher | Association for Computing Machinery (ACM) |
| Pages | 2896-2915 |
| Number of pages | 20 |
| ISBN (Electronic) | 9781611975994 |
| Publication status | Published - 1 Jan 2020 |
| Externally published | Yes |
| Event | Annual ACM-SIAM Symposium on Discrete Algorithms, 2020 - Hilton Salt Lake City Center, Salt Lake City, United States of America Duration: 5 Jan 2020 → 8 Jan 2020 Conference number: 31st https://www.siam.org/conferences/cm/conference/soda20 |
Publication series
| Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| Volume | 2020-January |
Conference
| Conference | Annual ACM-SIAM Symposium on Discrete Algorithms, 2020 |
|---|---|
| Abbreviated title | SODA20 |
| Country/Territory | United States of America |
| City | Salt Lake City |
| Period | 5/01/20 → 8/01/20 |
| Other | This 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 |