2026-08-02T16:50:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19313 2024-03-06T11:03:44Z ddc:004 open_access

Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width Bergougnoux, Benjamin Gajarský, Jakub Guśpiel, Grzegorz Hliněný, Petr Pokrývka, Filip Sokołowski, Marek twin-width tree-width excluded grid sparsity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Bergougnoux and Jakub Gajarský and Grzegorz Guśpiel and Petr Hliněný and Filip Pokrývka and Marek Sokołowski 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.11 urn:nbn:de:0030-drops-193130 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.11 eng https://creativecommons.org/licenses/by/4.0/legalcode