License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2021.6
URN: urn:nbn:de:0030-drops-153895
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15389/
Go to the corresponding LIPIcs Volume Portal

Balabán, Jakub ; Hliněný, Petr

Twin-Width Is Linear in the Poset Width

pdf-format:
LIPIcs-IPEC-2021-6.pdf (0.7 MB)

Abstract

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, Thomassé 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 8d with a direct and elementary argument, and show that this bound is tight up to a constant factor. Specifically, 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.

BibTeX - Entry

@InProceedings{balaban_et_al:LIPIcs.IPEC.2021.6,
  author =	{Balab\'{a}n, Jakub and Hlin\v{e}n\'{y}, Petr},
  title =	{{Twin-Width Is Linear in the Poset Width}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15389},
  URN =		{urn:nbn:de:0030-drops-153895},
  doi =		{10.4230/LIPIcs.IPEC.2021.6},
  annote =	{Keywords: twin-width, digraph, poset, FO model checking, contraction sequence}
}

Keywords: twin-width, digraph, poset, FO model checking, contraction sequence
Collection: 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Issue Date: 2021
Date of publication: 22.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI