LIPIcs.ESA.2019.34.pdf
- Filesize: 0.64 MB
- 13 pages
Document
Improved Bounds for the Excluded-Minor Approximation of Treedepth
Authors
-
Part of:
Volume:
27th Annual European Symposium on Algorithms (ESA 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-09-06
Cite As Get BibTex
Wojciech Czerwiński, Wojciech Nadara, and Marcin Pilipczuk. Improved Bounds for the Excluded-Minor Approximation of Treedepth. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 34:1-34:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.34
Abstract
Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in the theory of sparse graph classes. We show that there exists a constant C such that for every integers a,b >= 2 and a graph G, if the treedepth of G is at least Cab log a, then the treewidth of G is at least a or G contains a subcubic (i.e., of maximum degree at most 3) tree of treedepth at least b as a subgraph.
As a direct corollary, we obtain that every graph of treedepth Omega(k^3 log k) is either of treewidth at least k, contains a subdivision of full binary tree of depth k, or contains a path of length 2^k. This improves the bound of Omega(k^5 log^2 k) of Kawarabayashi and Rossman [SODA 2018].
We also show an application for approximation algorithms of treedepth: given a graph G of treedepth k and treewidth t, one can in polynomial time compute a treedepth decomposition of G of width O(kt log^{3/2} t). This improves upon a bound of O(kt^2 log t) stemming from a tradeoff between known results.
The main technical ingredient in our result is a proof that every tree of treedepth d contains a subcubic subtree of treedepth at least d * log_3 ((1+sqrt{5})/2).
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph theory
Keywords
- treedepth
- excluded minor
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Julia Chuzhoy and Zihan Tan. Towards Tight(er) Bounds for the Excluded Grid Theorem. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1445-1464. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.88.
- Zdenek Dvorak, Archontia C. Giannopoulou, and Dimitrios M. Thilikos. Forbidden graphs for tree-depth. Eur. J. Comb., 33(5):969-979, 2012. URL: https://doi.org/10.1016/j.ejc.2011.09.014.
- Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM J. Comput., 38(2):629-657, 2008. URL: https://doi.org/10.1137/05064299X.
- Ken-ichi Kawarabayashi and Benjamin Rossman. A Polynomial Excluded-Minor Approximation of Treedepth. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 234-246. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.17.
- Jeremy Kun, Michael P. O'Brien, and Blair D. Sullivan. Treedepth Bounds in Linear Colorings. CoRR, abs/1802.09665, 2018. URL: http://arxiv.org/abs/1802.09665.
- Jaroslav Nesetril and Patrice Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb., 27(6):1022-1041, 2006. URL: https://doi.org/10.1016/j.ejc.2005.01.010.
- Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
- Jaroslav Nesetril and Patrice Ossona de Mendez. On Low Tree-Depth Decompositions. Graphs and Combinatorics, 31(6):1941-1963, 2015. URL: https://doi.org/10.1007/s00373-015-1569-7.
- Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. A Faster Parameterized Algorithm for Treedepth. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 931-942. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_77.
-
Neil Robertson and Paul D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309-322, 1986.
- Alejandro A. Schäffer. Optimal Node Ranking of Trees in Linear Time. Inf. Process. Lett., 33(2):91-96, 1989. URL: https://doi.org/10.1016/0020-0190(89)90161-0.