License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2018.2
URN: urn:nbn:de:0030-drops-102033
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10203/
Go to the corresponding LIPIcs Volume Portal


Baste, Julien ; Sau, Ignasi ; Thilikos, Dimitrios M.

A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth

pdf-format:
LIPIcs-IPEC-2018-2.pdf (0.7 MB)


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
Seminar: 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Issue Date: 2019
Date of publication: 25.01.2019


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI