Twin-Width Is Linear in the Poset Width

Authors Jakub Balabán, Petr Hliněný



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.6.pdf
  • Filesize: 0.7 MB
  • 13 pages

Document Identifiers

Author Details

Jakub Balabán
  • Masaryk University, Brno, Czech Republic
Petr Hliněný
  • Masaryk University, Brno, Czech Republic

Cite AsGet BibTex

Jakub Balabán and Petr Hliněný. Twin-Width Is Linear in the Poset Width. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.6

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
  • Mathematics of computing → Graph algorithms
Keywords
  • twin-width
  • digraph
  • poset
  • FO model checking
  • contraction sequence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width III: max independent set and coloring. CoRR, abs/2007.14161, 2020. URL: http://arxiv.org/abs/2007.14161.
  2. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width II: small classes. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1977-1996. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.118.
  3. Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé. Twin-width IV: low complexity matrices. CoRR, abs/2102.03117, 2021. URL: http://arxiv.org/abs/2102.03117.
  4. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 601-612. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00062.
  5. Édouard Bonnet, Jaroslav Nešetřil, Patrice Ossona de Mendez, Sebastian Siebertz, and Stéphan Thomassé. Twin-width and permutations. CoRR, abs/2102.06880, 2021. URL: http://arxiv.org/abs/2102.06880.
  6. Simone Bova, Robert Ganian, and Stefan Szeider. Model checking existential logic on partially ordered sets. ACM Trans. Comput. Log., 17(2):10:1-10:35, 2016. URL: https://doi.org/10.1145/2814937.
  7. Jakub Gajarský, Petr Hliněný, Daniel Lokshtanov, Jan Obdržálek, Sebastian Ordyniak, M. S. Ramanujan, and Saket Saurabh. FO model checking on posets of bounded width. In FOCS, pages 963-974. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/FOCS.2015.63.
  8. Robert Ganian, Petr Hliněný, Daniel Král, Jan Obdržálek, Jarett Schwartz, and Jakub Teska. FO model checking of interval graphs. Log. Methods Comput. Sci., 11(4), 2015. URL: https://doi.org/10.2168/LMCS-11(4:11)2015.
  9. Petr Hliněný, Filip Pokrývka, and Bodhayan Roy. FO model checking on geometric graphs. Comput. Geom., 78:1-19, 2019. URL: https://doi.org/10.1016/j.comgeo.2018.10.001.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail