TY - GEN
T1 - A complexity dichotomy for hitting small planar minors parameterized by treewidth
AU - Baste, Julien
AU - Sau, Ignasi
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos; licensed under Creative Commons License CC-BY.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - 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 nvertex 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 2o(tw) · nO(1) under the ETH, and can be solved in time 2O(tw·log tw) · nO(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 = K1), we prove that 9 of them are solvable in time 2T(tw) · nO(1), and that the other 20 ones are solvable in time 2T(tw·log tw) · nO(1). Namely, we prove that K4 and the diamond are the only graphs on at most 4 vertices for which the problem is solvable in time 2T(tw·log tw) · nO(1), and that the chair and the banner are the only graphs on 5 vertices for which the problem is solvable in time 2T(tw) · nO(1). For the version of the problem where H is forbidden as a topological minor, the case H = K1,4 can be solved in time 2T(tw) · nO(1). This exhibits, to the best of our knowledge, the first difference between the computational complexity of both problems.
AB - 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 nvertex 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 2o(tw) · nO(1) under the ETH, and can be solved in time 2O(tw·log tw) · nO(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 = K1), we prove that 9 of them are solvable in time 2T(tw) · nO(1), and that the other 20 ones are solvable in time 2T(tw·log tw) · nO(1). Namely, we prove that K4 and the diamond are the only graphs on at most 4 vertices for which the problem is solvable in time 2T(tw·log tw) · nO(1), and that the chair and the banner are the only graphs on 5 vertices for which the problem is solvable in time 2T(tw) · nO(1). For the version of the problem where H is forbidden as a topological minor, the case H = K1,4 can be solved in time 2T(tw) · nO(1). This exhibits, to the best of our knowledge, the first difference between the computational complexity of both problems.
KW - Dynamic programming
KW - Exponential Time Hypothesis
KW - Graph minors
KW - Hitting minors
KW - Parameterized complexity
KW - Topological minors
KW - Treewidth
UR - http://www.scopus.com/inward/record.url?scp=85092551346&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85092551346&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.IPEC.2018.2
DO - 10.4230/LIPIcs.IPEC.2018.2
M3 - Conference contribution
AN - SCOPUS:85092551346
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 13th International Symposium on Parameterized and Exact Computation, IPEC 2018
A2 - Paul, Christophe
A2 - Pilipczuk, Michal
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 13th International Symposium on Parameterized and Exact Computation, IPEC 2018
Y2 - 22 August 2018 through 24 August 2018
ER -