Twin-Width is Linear in the Poset Width
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Twin-Width is Linear in the Poset Width
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA20-04567S" target="_blank" >GA20-04567S: Structure of tractable instances of hard algorithmic problems on graphs</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
International Symposium on Parameterized and Exact Computation (IPEC)
ISBN
9783959772167
ISSN
1868-8969
e-ISSN
—
Number of pages
13
Pages from-to
„6:1“-„6:13“
Publisher name
Schloss Dagstuhl -- Leibniz-Zentrum f{"u}r Informatik
Place of publication
Dagstuhl
Event location
Lisboa
Event date
Sep 8, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—