Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth

Authors Julien Baste, Ignasi Sau, Dimitrios M. Thilikos



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2017.4.pdf
  • Filesize: 0.72 MB
  • 12 pages

Document Identifiers

Author Details

Julien Baste
Ignasi Sau
Dimitrios M. Thilikos

Cite AsGet BibTex

Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.IPEC.2017.4

Abstract

For a fixed collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, decide whether there exists a subset S of V(G) of size at most k such that G-S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-DELETION when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F}, the smallest function f_F such that F-M-DELETION can be solved in time f_F(tw)n^{O(1)} on n-vertex graphs. Using and enhancing the machinery of boundaried graphs and small sets of representatives introduced by Bodlaender et al. [J ACM, 2016], we prove that when all the graphs in F are connected and at least one of them is planar, then f_F(w) = 2^{O(wlog w)}. When F is a singleton containing a clique, a cycle, or a path on i vertices, we prove the following asymptotically tight bounds: - f_{K_4}(w) = 2^{Theta(wlog w)}. - f_{C_i}(w) = 2^{Theta(w)} for every i<5, and f_{C_i}(w) = 2^{Theta(wlog w)} for every i>4. - f_{P_i}(w) = 2^{Theta(w)} for every i<5, and f_{P_i}(w) = 2^{Theta(wlog w)} for every i>5. The lower bounds hold unless the Exponential Time Hypothesis fails, and the superexponential ones are inspired by a reduction of Marcin Pilipczuk [Discrete Appl Math, 2016]. The single-exponential algorithms use, in particular, the rank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. We also consider the version of the problem where the graphs in F are forbidden as topological minors, and prove essentially the same set of results holds.
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

References

  1. Julien Baste, Marc Noy, and Ignasi Sau. On the number of labeled graphs of bounded treewidth. CoRR, abs/1604.07273, 2016. To appear in Proc. of WG 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, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (meta) kernelization. Journal of the ACM, 63(5):44:1-44:69, 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. CoRR, abs/1704.06757, 2017. Google Scholar
  5. Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. URL: http://dx.doi.org/10.1016/0890-5401(90)90043-H.
  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. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. In Proc. of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 470-479, 2012. Google Scholar
  8. 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
  9. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. In Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 503-510, 2010. Full version available at CoRR, abs/1606.05689, 2016. Google Scholar
  10. Valentin Garnero, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos. Explicit linear kernels via dynamic programming. SIAM Journal on Discrete Mathematics, 29(4):1864-1894, 2015. Google Scholar
  11. John E. Hopcroft and Robert Endre Tarjan. Efficient algorithms for graph manipulation. Communations of ACM, 16(6):372-378, 1973. Google Scholar
  12. 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
  13. 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
  14. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Transactions on Algorithms, 12(2):21:1-21:41, 2016. Google Scholar
  15. J. M. Lewis and M. Yannakakis. The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences, 20(2):219-230, 1980. Google Scholar
  16. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS, 105:41-72, 2011. Google Scholar
  17. 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
  18. Doowon Paik, Sudhakar M. Reddy, and Sartaj Sahni. Deleting vertices to bound path length. IEEE Trans. Computers, 43(9):1091-1096, 1994. URL: http://dx.doi.org/10.1109/12.312117.
  19. Marcin Pilipczuk. A tight lower bound for Vertex Planarization on graphs of bounded treewidth. Discrete Applied Mathematics, 231:211-216, 2017. Google Scholar
  20. Neil Robertson and Paul D. Seymour. Graph minors. X. Obstructions to tree decomposition. Journal of Combinatorial Theory, Series B, 52(2):153-190, 1991. 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