Hitting minors on bounded treewidth graphs. III. Lower bounds - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Journal of Computer and System Sciences Année : 2020

Hitting minors on bounded treewidth graphs. III. Lower bounds

Julien Baste
Ignasi Sau

Résumé

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.
Fichier principal
Vignette du fichier
JCSS-D-19-00030-R1.pdf (834.81 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-02989938 , version 1 (05-11-2020)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More