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 -