Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs

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 solution-size parameter).

1. $2^{O(\sqrt{k}\log k)}\cdot n^{O(1)}$ time algorithms for Edge Bipartization and Odd Cycle Transversal;
2. a $2^{O(\sqrt{k}{\log }^{4}k)}\cdot n^{O(1)}$ time algorithm for Edge Multiway Cut and a $2^{O(r\sqrt{k}\log k)}\cdot n^{O(1)}$ time algorithm for Vertex Multiway Cut, where $r$ is the number of terminals to be separated;
3. a $2^{O((r+\sqrt{k}){\log }^4(rk))}\cdot n^{O(1)}$ time algorithm for Edge Multicut and a $2^{O((\sqrt{rk}+r)\log (rk))}\cdot n^{O(1)}$ time algorithm for Vertex Multicut, where $r$ is the number of terminal pairs to be separated;
4. a $2^{O(\sqrt{k}\log g{\log }^{4}k)}\cdot n^{O(1)}$ time algorithm for Group Feedback Edge Set and a $2^{O(g\sqrt{k}\log (gk))}\cdot n^{O(1)}$ time algorithm for Group Feedback Vertex Set, where $g$ is the size of the group.
5. In addition, our approach also gives $n^{O(\sqrt{k})}$ time algorithms for all above problems with the exception of $n^{O(r+\sqrt{k})}$ time for Edge/Vertex Multicut and $(ng{)}^{O(\sqrt{k})}$ time for Group Feedback Edge/Vertex Set. We obtain our results by giving a new decomposition theorem on graphs of bounded genus, or more generally, an $h$-almost-embeddable graph for any fixed constant $h$. In particular we show the following. Let $G$ be an $h$-almost-embeddable graph for a constant $h$. Then for every $p\in \mathbb{N}$, there exist disjoint sets $Z_1,\dots ,Z_p\subseteq V(G)$ such that for every $i\in \{1,\dots ,p\}$ and every $Z^{\mathrm{\prime }}\subseteq Z_i$, the treewidth of $G\mathrm{/}(Z_i\mathrm{\backslash }{Z}^{\mathrm{\prime }})$ is $O(p+\mathrm{\mid }{Z}^{\mathrm{\prime }}\mathrm{\mid })$. Here $G\mathrm{/}(Z_i\mathrm{\backslash }{Z}^{\mathrm{\prime }})$ is the graph obtained from $G$ by contracting edges with both endpoints in $Z_i \backslash Z’$.