Other formats:
BibTeX
LaTeX
RIS
@inproceedings{2306239,
author = {Bergougnoux, Benjamin and Gajarský, Jakub and Guspiel, Grzegorz Jan and Hliněný, Petr and Pokrývka, Filip and Sokołowski, Marek},
address = {Dagstuhl, Germany},
booktitle = {ISAAC 2023},
doi = {http://dx.doi.org/10.4230/LIPICS.ISAAC.2023.11},
edition = {283},
keywords = {twin-width; tree-width; excluded grid; sparsity},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Dagstuhl, Germany},
isbn = {978-3-95977-289-1},
pages = {"11:1"-"11:13"},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
title = {Sparse Graphs of Twin-width 2 Have Bounded Tree-width},
year = {2023}
}
TY - JOUR
ID - 2306239
AU - Bergougnoux, Benjamin - Gajarský, Jakub - Guspiel, Grzegorz Jan - Hliněný, Petr - Pokrývka, Filip - Sokołowski, Marek
PY - 2023
TI - Sparse Graphs of Twin-width 2 Have Bounded Tree-width
PB - Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik
CY - Dagstuhl, Germany
SN - 9783959772891
KW - twin-width
KW - tree-width
KW - excluded grid
KW - sparsity
N2 - Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference of neighbourhoods of the vertices, and it can be seen as widely generalizing several other traditional structural parameters. Having such a sequence at hand allows to solve many otherwise hard problems efficiently. Our paper focuses on a comparison of twin-width to the more traditional tree-width on sparse graphs. Namely, we prove that if a graph G of twin-width at most 2 contains no K_{t,t} subgraph for some integer t, then the tree-width of G is bounded by a polynomial function of t. As a consequence, for any sparse graph class C we obtain a polynomial time algorithm which for any input graph G ∈ C either outputs a contraction sequence of width at most c (where c depends only on C), or correctly outputs that G has twin-width more than 2. On the other hand, we present an easy example of a graph class of twin-width 3 with unbounded tree-width, showing that our result cannot be extended to higher values of twin-width.
ER -
BERGOUGNOUX, Benjamin, Jakub GAJARSKÝ, Grzegorz Jan GUSPIEL, Petr HLINĚNÝ, Filip POKRÝVKA and Marek SOKOŁOWSKI. Sparse Graphs of Twin-width 2 Have Bounded Tree-width. Online. In \textit{ISAAC 2023}. 283rd ed. Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum f$\{\backslash$''u$\}$r Informatik, 2023, p.~''11:1''-''11:13'', 13 pp. ISBN~978-3-95977-289-1. Available from: https://dx.doi.org/10.4230/LIPICS.ISAAC.2023.11.
|
