Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds

摘要

For a fixed collection of graphs ${cal F}$, the ${cal F}$-M-DELETIONproblem consists in, given a graph $G$ and an integer $k$, decide whether thereexists $S subseteq V(G)$ with $|S| leq k$ such that $G setminus S$ does notcontain any of the graphs in ${cal F}$ as a minor. We are interested in theparameterized complexity of ${cal F}$-M-DELETION when the parameter is thetreewidth of $G$, denoted by $tw$. Our objective is to determine, for a fixed${cal F}$, the smallest function $f_{{cal F}}$ such that ${calF}$-M-DELETION can be solved in time $f_{{cal F}}(tw) cdot n^{O(1)}$ on$n$-vertex graphs. Using and enhancing the machinery of boundaried graphs andsmall sets of representatives introduced by Bodlaender et al. [J ACM, 2016], weprove that when all the graphs in ${cal F}$ are connected and at least one ofthem is planar, then $f_{{cal F}}(w) = 2^{O (w cdotlog w)}$. When ${cal F}$is a singleton containing a clique, a cycle, or a path on $i$ vertices, weprove the following asymptotically tight bounds: $ullet$ $f_{{K_4}}(w) = 2^{Theta (w cdot log w)}$. $ullet$ $f_{{C_i}}(w) = 2^{Theta (w)}$ for every $i leq 4$, and$f_{{C_i}}(w) = 2^{Theta (w cdotlog w)}$ for every $i geq 5$. $ullet$ $f_{{P_i}}(w) = 2^{Theta (w)}$ for every $i leq 4$, and$f_{{P_i}}(w) = 2^{Theta (w cdot log w)}$ for every $i geq 6$. The lower bounds hold unless the Exponential Time Hypothesis fails, and thesuperexponential ones are inspired by a reduction of Marcin Pilipczuk [DiscreteAppl Math, 2016]. The single-exponential algorithms use, in particular, therank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. Wealso consider the version of the problem where the graphs in ${cal F}$ areforbidden as topological minors, and prove that essentially the same set ofresults holds.