Hitting minors on bounded treewidth graphs
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos · arXiv (Cornell University) · 2017
For a fixed collection of graphs ${\cal F}$, the ${\cal F}$-M-Deletion problem consists in, given a graph $G$ and an integer $k$, decide whether there exists $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as a minor. We are interested in its parameterized complexity when the parameter is the treewidth of $G$, denoted by $tw$. Our objective is to determine, for a fixed ${\cal F}$, the smallest function $f_{\cal F}$ such that ${\cal F}$-M-Deletion can be solved in time $f_{\cal F}(tw) \cdot n^{O(1)}$ on $n$-vertex graphs. We prove that $f_{\cal F}(tw)=2^{2^{O(tw\log tw)}}$ for every collection ${\cal F}$, that $f_{\cal F}(tw)=2^{O(tw\log tw)}$ if all the graphs in ${\cal F}$ are connected and at least one of them is planar, and that $f_{\cal F}(tw)=2^{O(tw)}$ if in addition the input graph $G$ is planar or embedded in a surface. When ${\cal F}$ contains a single connected planar graph $H$, we obtain a tight dichotomy about the asymptotic complexity of $\{H\}$-M-Deletion. Namely, we prove that $f_{\{H\}}(tw)=2^{\Theta(tw)}$ if $H$ is a minor of the banner (that is, the graph consisting of a $C_4$ plus a pendent edge) that is different from $P_5$, and that $f_{\{H\}}(tw)=2^{\Theta(tw\log tw)}$ otherwise. All the lower bounds hold under the ETH. We also consider the version of the problem where the graphs in ${\cal F}$ are forbidden as topological minors, and prove similar results, except that, in the algorithms, instead of requiring ${\cal F}$ to contain a planar graph, we need it to contain a subcubic planar graph. We also prove that, for this problem, $f_{\{K_{1,i}\}}(tw)=2^{\Theta(tw)}$ for every $i \geq 1$, while for the minor version it holds that $f_{\{K_{1,i}\}}(tw)=2^{\Theta(tw\log tw)}$ for every $i \geq 4$.