Résumé
We design the first subexponential-time (parameterized) algorithms for several cut and cycle-hitting problems on H-minor free graphs. In particular, we obtain the following results (where k is the solutionsize parameter).
2(O(root k log k)) center dot n(O(1)) time algorithms for Edge Bipartization and Odd Cycle Transversal;
a 2(O(root k log4 k)) center dot n(O(1)) time algorithm for Edge Multiway Cut and a 2(O(r root k log k)) center dot n(O(1)) time algorithm for Vertex Multiway Cut (with undeletable terminals), where r is the number of terminals to be separated;
a 2(O((r+root k) log4( rk))) center dot n(O(1)) time algorithm for Edge Multicut and a 2(O((root rk+r) log(rk))) center dot n(O(1)) time algorithm for Vertex Multicut (with undeletable terminals), where r is the number of terminal pairs to be separated;
a 2(O(root k log g log4 k)) center dot n(O(1)) time algorithm for Group Feedback Edge Set and a 2(O(g root k log(gk))) center dot n(O(1)) time algorithm for Group Feedback Vertex Set, where g is the size of the group.
In addition, our approach also gives n(O(root k)) time algorithms for all above problems with the exception of n(O(r+root k)) time for Edge/Vertex Multicut and (ng)(O(root k)) time for Group Feedback Edge/Vertex Set.
All of our FPT algorithms (the first four items above) are randomized, as they use known randomized kernelization algorithms as sub-routines.
We obtain our results by giving a new decomposition theorem on graphs of bounded genus, or more generally, an h-almost-embeddable graph for an arbitrary but fixed constant h. Our new decomposition theorem generalizes known Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010] and H-minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. In particular we show the following. Let G be a graph of bounded genus, or more generally, an h-almost-embeddable graph for an arbitrary but fixed constant h. Then for every p epsilon N, there exist disjoint sets Z(1),..., Z(p) subset of V (G) such that for every i epsilon {1,..., p} and every Z' subset of Z(i), the treewidth of G/(Z(i)\Z') is upper bounded by O(p + |Z '|), where the constant hidden in O(center dot) depends on h. Here G/(Z(i)\Z ') denotes the graph obtained from G by contracting every edge with both endpoints in Z(i)\Z '. When Z' = circle divide, this corresponds to classical Contraction Decomposition Theorem.