Skip to Main content Skip to Navigation
Journal articles

Hitting minors on bounded treewidth graphs. III. Lower bounds

Julien Baste 1 Ignasi Sau Valls 1 Dimitrios M. Thilikos 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02989938
Contributor : Ignasi Sau <>
Submitted on : Thursday, November 5, 2020 - 12:53:41 PM
Last modification on : Friday, November 20, 2020 - 11:56:02 AM
Long-term archiving on: : Saturday, February 6, 2021 - 7:15:27 PM

File

JCSS-D-19-00030-R1.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Julien Baste, Ignasi Sau Valls, Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. III. Lower bounds. Journal of Computer and System Sciences, Elsevier, 2020, 109, pp.56-77. ⟨10.1016/j.jcss.2019.11.002⟩. ⟨lirmm-02989938⟩

Share

Metrics

Record views

36

Files downloads

46