Další formáty:
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 a Marek SOKOŁOWSKI. Sparse Graphs of Twin-width 2 Have Bounded Tree-width. Online. In \textit{ISAAC 2023}. 283. vyd. Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum f$\{\backslash$''u$\}$r Informatik, 2023, s.~''11:1''-''11:13'', 13 s. ISBN~978-3-95977-289-1. Dostupné z: https://dx.doi.org/10.4230/LIPICS.ISAAC.2023.11.
|