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}MDeletion, parameterized by the treewidth tw of the input graph: given an nvertex 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}MDeletion 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:12:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770842},
ISSN = {18688969},
year = {2019},
volume = {115},
editor = {Christophe Paul and Michal Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10203},
URN = {urn:nbn:de:0030drops102033},
doi = {10.4230/LIPIcs.IPEC.2018.2},
annote = {Keywords: parameterized complexity, graph minors, treewidth, hitting minors, topological minors, dynamic programming, Exponential Time Hypothesis}
}
05.02.2019
Keywords: 

parameterized complexity, graph minors, treewidth, hitting minors, topological minors, dynamic programming, Exponential Time Hypothesis 
Seminar: 

13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Issue date: 

2019 
Date of publication: 

05.02.2019 