Improved bounds for the excluded-minor approximation of treedepth
share
Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays 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 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 Ω(k^3 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 Ω(k^5 ^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 ^3/2 t). This improves upon a bound of O(kt^2 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 ·_3 ((1+√(5))/2).
READ FULL TEXT