Hitting minors on bounded treewidth graphs. Ⅲ. Lower bounds

摘要

For a finite fixed collection of graphs F, the F-M-Deletion problem consists in, given a graph G and an integer κ, decide whether there exists S≤V(G) with |S|≤κ such that GS 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)·n～(o(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～(Ω(tm)), even if G is planar. Our main result is that if F contains a single connected graph H that is either P_5 or is not a minor of the banner, then fF(tw) = 2～(Ω(tm·logtw)).