Hitting minors on bounded treewidth graphs. III. Lower bounds

For a finite collection of graphs $\mathcal{F}$, the $\mathcal{F}$-M-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. 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 $\mathcal{F}$, the smallest function $f_{\mathcal{F}}$ such that ${\cal F}$-M-DELETIONcanbesolvedintime$f_{{\cal F}}(tw) \cdot n^{O(1)}$on$n$-vertexgraphs\mathrm{.}WeprovidelowerboundsundertheETHon$f_{{\cal F}}$ for several collections $\mathcal{F}$. We first prove that for any $\mathcal{F}$ containing connected graphs of size at least two, $f_{{\cal F}}(tw)= 2^{\Omega(tw)}$,eveniftheinputgraph$G$ is planar. Our main contribution consists of superexponential lower bounds for a number of collections ${\cal F}$, inspired by a reduction of Bonnet et al.~[IPEC, 2017]. In particular, we prove that when $\mathcal{F}$ contains a single connected graph $H$ that is either $P_5$ or is not a minor of the banner (that is, the graph consisting of a $C_4$ plus a pendent edge), then $f_{\mathcal{F}}(tw)=2^{\mathrm{\Omega }(tw\cdot \log tw)}$. This is the third 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$, when $H$ is connected.