A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth

Abstract : 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
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02342806
Contributor : Dimitrios Thilikos <>
Submitted on : Friday, November 1, 2019 - 12:53:33 PM
Last modification on : Monday, January 13, 2020 - 1:15:17 AM

File

LIPIcs-IPEC-2018-2.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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

Share

Metrics

Record views

13

Files downloads

19