Improved bounds for the excluded-minor approximation of treedepth
Improved bounds for the excluded-minor approximation of treedepth
复制标题
改进了树深度的排除次要近似值的界限
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Marcin Pilipczuk
中科院分区：
文献类型：
--
作者：
Wojciech Czerwinski;Wojciech Nadara;Marcin Pilipczuk
树深是一个比树宽和路宽更严格的图宽参数，在稀疏图类理论中起着重要作用。我们证明了存在一个常数C使得对任意正整数a，B和图G，如果G的树深至少为Ca B，则G的树宽至少为a或G包含一个次立方（即，树深度至少为$B $的树作为子图。
作为一个直接推论，我们得到了树深为Ω（k^3）$的图要么树宽至少为k$，要么包含深度为k$的满二叉树的一个剖分，要么包含长度为2^k $的路。这改进了Kawarabayashi和Rossman的$Omega（k^5 log^2 k）$的界[SODA 2018]。
我们还展示了我们的技术的树深度的近似算法的应用程序：给定一个图$G$的树深度$k$和树宽度$t$，可以在多项式时间计算的树深度分解$G$的宽度$mathcal{O}（kt log^{3/2} t）$。这改进了源于已知结果之间的折衷的$mathcal{O}（kt^2 log t）$的界限。
在我们的结果中的主要技术成分是一个证明，每棵树的深度$d$包含一个子立方体的子树的树深度至少$d cdot log_3（（1+sqrt{5}）/2）$。
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 positive integers $a,b$ and a graph $G$, if the treedepth of $G$ is at least $Cab$, 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)$ 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 of our techniques 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 $mathcal{O}(kt log^{3/2} t)$. This improves upon a bound of $mathcal{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 cdot log_3 ((1+sqrt{5})/2)$.
一种更快的树深度参数化算法
DOI：
10.1007/978-3-662-43948-7_77
发表时间：
2014
期刊：
影响因子：
--
作者：
Felix Reidl;Peter Rossmanith;Fernando Sánchez Villaamil;Somnath Sikdar
通讯作者：
Somnath Sikdar