2026-07-23T04:27:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10203 2024-03-06T10:44:14Z ddc:004 open_access

A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth Baste, Julien Sau, Ignasi Thilikos, Dimitrios M. parameterized complexity graph minors treewidth hitting minors topological minors dynamic programming Exponential Time Hypothesis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julien Baste and Ignasi Sau and Dimitrios M. Thilikos 2019 Is Part Of LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2018.2 urn:nbn:de:0030-drops-102033 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.2 eng https://creativecommons.org/licenses/by/3.0/legalcode