Sparse Graphs of Twin-width 2 Have Bounded Tree-width

D 2023

Sparse Graphs of Twin-width 2 Have Bounded Tree-width

BERGOUGNOUX, Benjamin, Jakub GAJARSKÝ, Grzegorz Jan GUSPIEL, Petr HLINĚNÝ, Filip POKRÝVKA et. al.

Základní údaje

Originální název

Sparse Graphs of Twin-width 2 Have Bounded Tree-width

Autoři

BERGOUGNOUX, Benjamin (250 Francie), Jakub GAJARSKÝ (703 Slovensko), Grzegorz Jan GUSPIEL (616 Polsko, domácí), Petr HLINĚNÝ (203 Česká republika, garant, domácí), Filip POKRÝVKA (703 Slovensko, domácí) a Marek SOKOŁOWSKI (616 Polsko)

Vydání

283. vyd. Dagstuhl, Germany, ISAAC 2023, od s. "11:1"-"11:13", 13 s. 2023

Nakladatel

Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/23:00131580

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-289-1

ISSN

DOI

http://dx.doi.org/10.4230/LIPICS.ISAAC.2023.11

Klíčová slova anglicky

twin-width; tree-width; excluded grid; sparsity

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 7. 4. 2024 23:19, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Návaznosti

MUNI/A/1081/2022, interní kód MU

Název: Modelování, analýza a verifikace (2023)

Investor: Masarykova univerzita, Modelování, analýza a verifikace (2023)

MUNI/A/1433/2022, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 23

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 23

Citovat

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 ISAAC 2023. 283. vyd. Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum f{\"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.

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

Podrobný výpis o publikaci