Loading Events

« All Events

  • This event has passed.
:

Tony Huynh, Stable sets in graphs with bounded odd cycle packing number

November 12 Tuesday @ 4:30 PM - 5:30 PM

Room B232, IBS (기초과학연구원)

It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs.  The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles.  The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$.  We prove that under the additional assumption that the input graph is embedded in a surface of bounded genus, there is a polynomial-time algorithm for each fixed $k$.  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ős-Pósa property in graphs embedded in a fixed surface. This result may be of independent interest and extends a theorem of Kawarabayashi and Nakamoto asserting that odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed orientable surface.

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 we prove to be efficiently solvable in our case.

This is joint work with Michele Conforti, Samuel Fiorini, Gwenaël Joret, and Stefan Weltge.

Details

Date:
November 12 Tuesday
Time:
4:30 PM - 5:30 PM
Event Category:
Event Tags:

Venue

Room B232
IBS (기초과학연구원)

Organizer

Sang-il Oum