Twin-Width is Linear in the Poset Width

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F21%3A00119289" target="_blank" >RIV/00216224:14330/21:00119289 - isvavai.cz</a>

Výsledek na webu

<a href="https://arxiv.org/abs/2106.15337" target="_blank" >https://arxiv.org/abs/2106.15337</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.IPEC.2021.6" target="_blank" >10.4230/LIPIcs.IPEC.2021.6</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Twin-Width is Linear in the Poset Width

Popis výsledku v původním jazyce

Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices, and it extends also to other binary relational structures, e.g. to digraphs and posets. It was introduced just very recently, in 2020 by Bonnet, Kim, Thomasse and Watrigant. One of the core results of these authors is that FO model checking on graph classes of bounded twin-width is in FPT. With that result, they also claimed that posets of bounded width have bounded twin-width, thus capturing prior result on FO model checking of posets of bounded width in FPT. However, their translation from poset width to twin-width was indirect and giving only a very loose double-exponential bound. We prove that posets of width d have twin-width at most 9d with a direct and elegant argument, and show that this bound is asymptotically tight. Specially, for posets of width 2 we prove that in the worst case their twin-width is also equal 2. These two theoretical results are complemented with straightforward algorithms to construct the respective contraction sequence for a given poset.

Název v anglickém jazyce

Twin-Width is Linear in the Poset Width

Popis výsledku anglicky

Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices, and it extends also to other binary relational structures, e.g. to digraphs and posets. It was introduced just very recently, in 2020 by Bonnet, Kim, Thomasse and Watrigant. One of the core results of these authors is that FO model checking on graph classes of bounded twin-width is in FPT. With that result, they also claimed that posets of bounded width have bounded twin-width, thus capturing prior result on FO model checking of posets of bounded width in FPT. However, their translation from poset width to twin-width was indirect and giving only a very loose double-exponential bound. We prove that posets of width d have twin-width at most 9d with a direct and elegant argument, and show that this bound is asymptotically tight. Specially, for posets of width 2 we prove that in the worst case their twin-width is also equal 2. These two theoretical results are complemented with straightforward algorithms to construct the respective contraction sequence for a given poset.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA20-04567S" target="_blank" >GA20-04567S: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

International Symposium on Parameterized and Exact Computation (IPEC)

ISBN

9783959772167

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

13

Strana od-do

„6:1“-„6:13“

Název nakladatele

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

Místo vydání

Dagstuhl

Místo konání akce

Lisboa

Datum konání akce

8. 9. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—