Hitting minors on bounded treewidth graphs. III. Lower bounds
share
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 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.
READ FULL TEXT