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.

Basic information

Original name

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

Authors

BERGOUGNOUX, Benjamin (250 France), Jakub GAJARSKÝ (703 Slovakia), Grzegorz Jan GUSPIEL (616 Poland, belonging to the institution), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution), Filip POKRÝVKA (703 Slovakia, belonging to the institution) and Marek SOKOŁOWSKI (616 Poland)

Edition

283. vyd. Dagstuhl, Germany, ISAAC 2023, p. "11:1"-"11:13", 13 pp. 2023

Publisher

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

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

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

Publication form

electronic version available online

RIV identification code

RIV/00216224:14330/23:00131580

Organization unit

Faculty of Informatics

ISBN

978-3-95977-289-1

ISSN

DOI

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

Keywords in English

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

Abstract

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.

Links

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

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

Investor: Masaryk University

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

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

Investor: Masaryk University

Citovat

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

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

Detailed Information on Publication Record