Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BY - Uznanie autorstwaImproved Bounds for the Excluded-Minor Approximation of Treedepth
| dc.abstract.en | 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). |
| dc.affiliation | Uniwersytet Warszawski |
| dc.conference.country | Niemcy |
| dc.conference.datefinish | 2019-09-13 |
| dc.conference.datestart | 2019-09-09 |
| dc.conference.place | Monachium |
| dc.conference.series | European Symposium on Algorithms |
| dc.conference.series | European Symposium on Algorithms |
| dc.conference.seriesshortcut | ESA |
| dc.conference.shortcut | ESA 2019 |
| dc.conference.weblink | http://esa-symposium.org/ |
| dc.contributor.author | Pilipczuk, Marcin |
| dc.contributor.author | Nadara, Wojciech |
| dc.contributor.author | Czerwiński, Wojciech |
| dc.date.accessioned | 2024-01-25T03:57:43Z |
| dc.date.available | 2024-01-25T03:57:43Z |
| dc.date.copyright | 2019-09-06 |
| dc.date.issued | 2019 |
| dc.description.accesstime | AT_PUBLICATION |
| dc.description.finance | Nie dotyczy |
| dc.description.version | FINAL_PUBLISHED |
| dc.description.volume | 144 |
| dc.identifier.doi | 10.4230/LIPICS.ESA.2019.34 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/109095 |
| dc.identifier.weblink | https://drops.dagstuhl.de/opus/volltexte/2019/11155/ |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.pages | 34:1--34:13 |
| dc.rights | CC-BY |
| dc.sciencecloud | nosend |
| dc.subject.en | treedepth |
| dc.subject.en | excluded minor |
| dc.title | Improved Bounds for the Excluded-Minor Approximation of Treedepth |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |