Twin-Width is Linear in the Poset Width

D 2021

Twin-Width is Linear in the Poset Width

BALABÁN, Jakub a Petr HLINĚNÝ

Základní údaje

Originální název

Twin-Width is Linear in the Poset Width

Autoři

BALABÁN, Jakub (203 Česká republika, domácí) a Petr HLINĚNÝ (203 Česká republika, garant, domácí)

Vydání

214. vyd. Dagstuhl, International Symposium on Parameterized and Exact Computation (IPEC), od s. "6:1"-"6:13", 13 s. 2021

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"

Odkazy

URL

Kód RIV

RIV/00216224:14330/21:00119289

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-216-7

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.IPEC.2021.6

Klíčová slova anglicky

twin-width; digraph; poset; FO model checking; contraction sequence

Štítky

core_B, firank_B, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 19. 4. 2022 10:03, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

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ávaznosti

GA20-04567S, projekt VaV

Název: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech

Investor: Grantová agentura ČR, Structure of tractable instances of hard algorithmic problems on graphs

MUNI/A/1108/2020, interní kód MU

Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X. (Akronym: SV-FI MAV X.)

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X.

Citovat

BALABÁN, Jakub a Petr HLINĚNÝ. Twin-Width is Linear in the Poset Width. Online. In Golovach, Petr A. and Zehavi, Meirav. International Symposium on Parameterized and Exact Computation (IPEC). 214. vyd. Dagstuhl: Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik, 2021, s. "6:1"-"6:13", 13 s. ISBN 978-3-95977-216-7. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.IPEC.2021.6.

@inproceedings{1799080,
   author = {Balabán, Jakub and Hliněný, Petr},
   address = {Dagstuhl},
   booktitle = {International Symposium on Parameterized and Exact Computation (IPEC)},
   doi = {http://dx.doi.org/10.4230/LIPIcs.IPEC.2021.6},
   edition = {214},
   editor = {Golovach, Petr A. and Zehavi, Meirav},
   keywords = {twin-width; digraph; poset; FO model checking; contraction sequence},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl},
   isbn = {978-3-95977-216-7},
   pages = {"6:1"-"6:13"},
   publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
   title = {Twin-Width is Linear in the Poset Width},
   url = {https://arxiv.org/abs/2106.15337},
   year = {2021}
}

TY  - JOUR
ID  - 1799080
AU  - Balabán, Jakub - Hliněný, Petr
PY  - 2021
TI  - Twin-Width is Linear in the Poset Width
PB  - Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik
CY  - Dagstuhl
SN  - 9783959772167
KW  - twin-width
KW  - digraph
KW  - poset
KW  - FO model checking
KW  - contraction sequence
UR  - https://arxiv.org/abs/2106.15337
N2  - 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.
ER  -

BALABÁN, Jakub a Petr HLINĚNÝ. Twin-Width is Linear in the Poset Width. Online. In Golovach, Petr A. and Zehavi, Meirav. \textit{International Symposium on Parameterized and Exact Computation (IPEC)}. 214. vyd. Dagstuhl: Schloss Dagstuhl -- Leibniz-Zentrum f$\{\backslash$''u$\}$r Informatik, 2021, s.~''6:1''-''6:13'', 13 s. ISBN~978-3-95977-216-7. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.IPEC.2021.6.

Podrobný výpis o publikaci