A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2019

A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth

Résumé

For a fixed graph H, we are interested in the parameterized complexity of the following problem, called {H}-M-Deletion, parameterized by the treewidth tw of the input graph: given an n-vertex graph G and an integer k, decide whether there exists S ⊆ V (G) with |S| ≤ k such that G\S does not contain H as a minor. In previous work [IPEC, 2017] we proved that if H is planar and connected, then the problem cannot be solved in time 2 o(tw) · n O(1) under the ETH, and can be solved in time 2 O(tw·log tw) · n O(1). In this article we manage to classify the optimal asymptotic complexity of {H}-M-Deletion when H is a connected planar graph on at most 5 vertices. Out of the 29 possibilities (discarding the trivial case H = K 1), we prove that 9 of them are solvable in time 2 Θ(tw) · n O(1) , and that the other 20 ones are solvable in time 2 Θ(tw·log tw) · n O(1). Namely, we prove that K 4 and the diamond are the only graphs on at most 4 vertices for which the problem is solvable in time 2 Θ(tw·log tw) · n O(1) , and that the chair and the banner are the only graphs on 5 vertices for which the problem is solvable in time 2 Θ(tw) · n O(1). For the version of the problem where H is forbidden as a topological minor, the case H = K 1,4 can be solved in time 2 Θ(tw) · n O(1). This exhibits, to the best of our knowledge, the first difference between the computational complexity of both problems. 2012 ACM Subject Classification Mathematics of computing → Graph algorithms, Theory of computation → Parameterized complexity and exact algorithms
Fichier principal
Vignette du fichier
LIPIcs-IPEC-2018-2.pdf (713.64 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-02342806 , version 1 (01-11-2019)

Licence

Identifiants

Citer

Julien Baste, Ignasi Sau, Dimitrios M. Thilikos. A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth. IPEC 2018 - 13th International Symposium on Parameterized and Exact Computation, Aug 2018, Helsinki, Finland. pp.2:1--2:13, ⟨10.4230/LIPIcs.IPEC.2018.2⟩. ⟨lirmm-02342806⟩
85 Consultations
57 Téléchargements

Altmetric

Partager

More