Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms

For a finite collection of graphs $\mathcal{F}$, the $\mathcal{F}$-M-DELETION (resp. $\mathcal{F}$-TM-DELETION) problem consists in, given a graph $G$ and an integer $k$, decide whether there exists $S\subseteq V(G)$ with $\mathrm{\mid }S\mathrm{\mid }\le k$ such that $G\setminus S$ does not contain any of the graphs in $\mathcal{F}$ as a minor (resp. topological minor). We are interested in the parameterized complexity of both problems when the parameter is the treewidth of $G$, denoted by $tw$, and specifically in the cases where $\mathcal{F}$ contains a single connected planar graph $H$. We present algorithms running in time $2^{O(tw)} \cdot n^{O(1)}$,calledsingle-exponential,when$H$iseither$P_3$,$P_4$,$C_4$,thepaw,thechair,andthebannerforboth${H}$-M-DELETIONand${H}$-TM-DELETION,andwhen$H=K_{1,i}$,with$i \geq 1$,for${H}$-TM-DELETION. Some of these algorithms use the rank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. This is the second of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of $\{H\}$-M-DELETION in terms of $H$.