License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2018.2
URN: urn:nbn:de:0030-drops-102033
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10203/
Baste, Julien ;
Sau, Ignasi ;
Thilikos, Dimitrios M.
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 subseteq V(G) with |S| <= k such that G setminus 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^{Theta (tw)} * n^{O(1)}, and that the other 20 ones are solvable in time 2^{Theta (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^{Theta (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^{Theta (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^{Theta (tw)} * n^{O(1)}. This exhibits, to the best of our knowledge, the first difference between the computational complexity of both problems.
BibTeX - Entry
@InProceedings{baste_et_al:LIPIcs:2019:10203,
author = {Julien Baste and Ignasi Sau and Dimitrios M. Thilikos},
title = {{A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth}},
booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
pages = {2:1--2:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-084-2},
ISSN = {1868-8969},
year = {2019},
volume = {115},
editor = {Christophe Paul and Michal Pilipczuk},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10203},
URN = {urn:nbn:de:0030-drops-102033},
doi = {10.4230/LIPIcs.IPEC.2018.2},
annote = {Keywords: parameterized complexity, graph minors, treewidth, hitting minors, topological minors, dynamic programming, Exponential Time Hypothesis}
}
|
Keywords: |
|
parameterized complexity, graph minors, treewidth, hitting minors, topological minors, dynamic programming, Exponential Time Hypothesis |
|
Collection: |
|
13th International Symposium on Parameterized and Exact Computation (IPEC 2018) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
05.02.2019 |
