Abstract
For a finite collection of graphs F, the F-M-Deletion problem consists in, given a graph G and an integer k, decide whether there exists S ⊆ V (G) with |S| ≤ k such that G \ S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-Deletion when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F, the smallest function f F such that F-M-Deletion can be solved in time f F (tw) · n O(1) on n-vertex graphs. We provide lower bounds under the ETH on f F for several collections F. We first prove that for any F containing connected graphs of size at least two, f F (tw) = 2 Ω(tw) , even if the input graph G is planar. Our main contribution consists of superexponential lower bounds for a number of collections F, inspired by a reduction of Bonnet et al. [IPEC, 2017]. In particular, we prove that when 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 F (tw) = 2 Ω(tw·log tw). This is the third of a series of articles on this topic, and the lower bounds given here together with the algorithms given in the first two articles yield a dichotomy on the complexity of {H}-M-Deletion in terms of H, when H is a connected planar graph with |V (H)| ≥ 2. Namely, f {H} (tw) = 2 Θ(tw) if H is a minor of the banner that is different from P 5 , and f {H} (tw) = 2 Θ(tw·log tw) otherwise.