Document Open Access Logo

A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth

Authors Julien Baste, Ignasi Sau , Dimitrios M. Thilikos

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.2.pdf
  • Filesize: 0.69 MB
  • 13 pages

Document Identifiers

Author Details

Julien Baste
  • Sorbonne Université, Laboratoire d'Informatique de Paris 6, LIP6, Paris, France
Ignasi Sau
  • LIRMM, CNRS, Université de Montpellier, Montpellier, France
Dimitrios M. Thilikos
  • LIRMM, CNRS, Université de Montpellier, Montpellier, France, and, Department of Mathematics, National and Kapodistrian University of Athens, Greece

Funding

Work supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010).

Cite As Get BibTex

Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2018.2

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • parameterized complexity
  • graph minors
  • treewidth
  • hitting minors
  • topological minors
  • dynamic programming
  • Exponential Time Hypothesis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

  • All the results and proofs of this article, as well as those of [Julien Baste et al., 2017] and some other ones, are permanently available at https://arxiv.org/abs/1704.07284.

References

  1. Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth. In Proc. of the 12th International Symposium on Parameterized and Exact Computation (IPEC), volume 89 of LIPIcs, pages 4:1-4:12, 2017. Google Scholar
  2. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Information and Computation, 243:86-111, 2015. Google Scholar
  3. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^k n 5-Approximation Algorithm for Treewidth. SIAM Journal on Computing, 45(2):317-378, 2016. Google Scholar
  4. Édouard Bonnet, Nick Brettell, O-joung Kwon, and Dániel Marx. Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms. In Proc. of the 12th International Symposium on Parameterized and Exact Computation (IPEC), volume 89 of LIPIcs, pages 7:1-7:13, 2017. Google Scholar
  5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  6. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. In Proc. of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 150-159, 2011. Google Scholar
  7. Reinhard Diestel. Graph Theory, volume 173. Springer-Verlag, 4th edition, 2010. Google Scholar
  8. R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  9. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms. Journal of the ACM, 63(4):29:1-29:60, 2016. Google Scholar
  10. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  11. Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A Near-Optimal Planarization Algorithm. In Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1802-1811, 2014. Google Scholar
  12. T. Kloks. Treewidth. Computations and Approximations. Springer-Verlag LNCS, 1994. Google Scholar
  13. Tomasz Kociumaka and Marcin Pilipczuk. Deleting vertices to graphs of bounded genus. CoRR, abs/1706.04065, 2017. URL: http://arxiv.org/abs/1706.04065.
  14. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly Superexponential Parameterized Problems. In Proc. of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 760-776, 2011. Google Scholar
  15. Marcin Pilipczuk. A tight lower bound for Vertex Planarization on graphs of bounded treewidth. Discrete Applied Mathematics, 231:211-216, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact