Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos · SIAM Journal on Discrete Mathematics · 2020
For a finite collection of graphs ${\cal F}$, the $\mathcal{F}$-M-Deletion problem consists in, given a graph $G$ and an integer $k$, deciding 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 the parameterized complexity of $\mathcal{F}$-M-Deletion 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 $\mathcal{F}$-M-Deletion can be solved in time $f_{{\cal F}}({tw}) \cdot n^{\mathcal{O}(1)}$ on $n$-vertex graphs. We prove that $f_{{\cal F}}({tw}) = 2^{2^{\mathcal{O} ({tw} \cdot\log {tw})}}$ for every collection ${\cal F}$, that $f_{{\cal F}}({tw}) = 2^{\mathcal{O} ({tw} \cdot\log {tw})}$ if ${\cal F}$ contains a planar graph, and that $f_{{\cal F}}({tw}) = 2^{\mathcal{O} ({tw})}$ if in addition the input graph $G$ is planar or embedded in a surface. We also consider the version of the problem where the graphs in ${\cal F}$ are forbidden as topological minors, called $\mathcal{F}$-TM-Deletion. We prove similar results for this problem, except that in the last two algorithms, instead of requiring $\mathcal{F}$ to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic.