License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.34
URN: urn:nbn:de:0030-drops-111557
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11155/
Go to the corresponding LIPIcs Volume Portal

Czerwinski, Wojciech ; Nadara, Wojciech ; Pilipczuk, Marcin

Improved Bounds for the Excluded-Minor Approximation of Treedepth

pdf-format:
LIPIcs-ESA-2019-34.pdf (0.6 MB)

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).

BibTeX - Entry

@InProceedings{czerwinski_et_al:LIPIcs:2019:11155,
  author =	{Wojciech Czerwinski and Wojciech Nadara and Marcin Pilipczuk},
  title =	{{Improved Bounds for the Excluded-Minor Approximation of Treedepth}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{34:1--34:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11155},
  URN =		{urn:nbn:de:0030-drops-111557},
  doi =		{10.4230/LIPIcs.ESA.2019.34},
  annote =	{Keywords: treedepth, excluded minor}
}

Keywords: treedepth, excluded minor
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI