2021/11/28 by Bandyapadhyay, Sayan, Lochet, William, Lokshtanov, Daniel +2
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2111.14196
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. 2O(√(k)log k) ⋅ nO(1) time algorithms for Edge Bipartization and Odd Cycle Transversal; 2. a 2O(√(k)log4 k) ⋅ nO(1) time algorithm for Edge Multiway Cut and a 2O(r √(k) log k) ⋅ nO(1) time algorithm for Vertex Multiway Cut, where r is the number of terminals to be separated; 3. a 2O((r+√(k))log4 (rk)) ⋅ nO(1) time algorithm for Edge Multicut and a 2O((√(rk)+r) log (rk)) ⋅ nO(1) time algorithm for Vertex Multicut, where r is the number of terminal pairs to be separated; 4. a 2O(√(k) log g log4 k) ⋅ nO(1) time algorithm for Group Feedback Edge Set and a 2O(g √(k)log(gk)) ⋅ nO(1) time algorithm for Group Feedback Vertex Set, where g is the size of the group. 5. In addition, our approach also gives nO(√(k)) time algorithms for all above problems with the exception of nO(r+√(k)) time for Edge/Vertex Multicut and (ng)O(√(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∈ℕ, there exist disjoint sets Z1,…,Zp ⊆ V(G) such that for every i ∈ \1,…,p\ and every Z'⊆ Zi, the treewidth of G/(Zi\backslash Z') is O(p+|Z'|). Here G/(Zi\backslash Z') is the graph obtained from G by contracting edges with both endpoints in Zi \backslash Z'.