2026-07-21T20:21:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11155 2024-03-06T10:47:35Z ddc:004 open_access

Improved Bounds for the Excluded-Minor Approximation of Treedepth Czerwiński, Wojciech Nadara, Wojciech Pilipczuk, Marcin treedepth excluded minor 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wojciech Czerwiński and Wojciech Nadara and Marcin Pilipczuk 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.34 urn:nbn:de:0030-drops-111557 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.34 eng https://creativecommons.org/licenses/by/3.0/legalcode