Hitting minors on bounded treewidth graphs. III. Lower bounds

摘要

For a finite fixed 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 provide lower bounds under the ETH on the smallest function fF such that F-M-Deletion can be solved in time fF(tw)⋅nO(1) on n-vertex graphs, where tw denotes the treewidth of G. We first prove that for any F containing connected graphs of size at least two, fF(tw)=2Ω(tw), even if G is planar. Our main result is that if F contains a single connected graph H that is either P5 or is not a minor of the banner, then fF(tw)=2Ω(tw⋅log⁡tw).