Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Twin-Width VIII: Delineation and Win-Wins

Authors Édouard Bonnet , Dibyayan Chakraborty, Eun Jung Kim , Noleen Köhler , Raul Lopes , Stéphan Thomassé

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2022.9.pdf
  • Filesize: 0.92 MB
  • 18 pages

Document Identifiers

Author Details

Édouard Bonnet
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
Dibyayan Chakraborty
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
Eun Jung Kim
  • Université Paris-Dauphine, PSL University, CNRS UMR7243, LAMSADE, Paris, France
Noleen Köhler
  • Université Paris-Dauphine, PSL University, CNRS UMR7243, LAMSADE, Paris, France
Raul Lopes
  • Université Paris-Dauphine, PSL University, CNRS UMR7243, LAMSADE, Paris, France
Stéphan Thomassé
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France

Cite AsGet BibTex

Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, and Stéphan Thomassé. Twin-Width VIII: Delineation and Win-Wins. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.IPEC.2022.9

Abstract

We introduce the notion of delineation. A graph class C is said delineated by twin-width (or simply, delineated) if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if D is monadically dependent. An effective strengthening of delineation for a class C implies that tractable FO model checking on C is perfectly understood: On hereditary closures of subclasses D of C, FO model checking on D is fixed-parameter tractable (FPT) exactly when D has bounded twin-width. Ordered graphs [BGOdMSTT, STOC '22] and permutation graphs [BKTW, JACM '22] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, rooted directed path graphs are delineated. On the other hand, we observe or show that segment graphs, directed path graphs (with arbitrarily many roots), and visibility graphs of simple polygons are not delineated. In an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not), we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW, SODA '21]. We show that K_{t,t}-free segment graphs, and axis-parallel H_t-free unit segment graphs have bounded twin-width, where H_t is the half-graph or ladder of height t. In contrast, axis-parallel H₄-free two-lengthed segment graphs have unbounded twin-width. We leave as an open question whether unit segment graphs are delineated. More broadly, we explore which structures (large bicliques, half-graphs, or independent sets) are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Our new results, combined with the FPT algorithm for first-order model checking on graphs given with O(1)-sequences [BKTW, JACM '22], give rise to a variety of algorithmic win-win arguments. They all fall in the same framework: If p is an FO definable graph parameter that effectively functionally upperbounds twin-width on a class C, then p(G) ⩾ k can be decided in FPT time f(k) ⋅ |V(G)|^O(1). For instance, we readily derive FPT algorithms for k-Ladder on visibility graphs of 1.5D terrains, and k-Independent Set on visibility graphs of simple polygons. This showcases that the theory of twin-width can serve outside of classes of bounded twin-width.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Fixed parameter tractability
Keywords
  • Twin-width
  • intersection graphs
  • visibility graphs
  • monadic dependence and stability
  • first-order model checking

Metrics

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

Related Versions

References

  1. John T. Baldwin and Saharon Shelah. Second-order quantifiers and the complexity of theories. Notre Dame Journal of Formal Logic, 26(3):229-303, 1985. Google Scholar
  2. Boaz Ben-Moshe, Matthew J. Katz, and Joseph S. B. Mitchell. A constant-factor approximation algorithm for optimal 1.5D terrain guarding. SIAM J. Comput., 36(6):1631-1647, 2007. URL: https://doi.org/10.1137/S0097539704446384.
  3. Pierre Bergé, Édouard Bonnet, and Hugues Déprés. Deciding twin-width at most 4 is NP-complete. CoRR, abs/2112.08953, 2021. URL: http://arxiv.org/abs/2112.08953.
  4. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width II: small classes. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1977-1996, 2021. URL: https://doi.org/10.1137/1.9781611976465.118.
  5. Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk. Twin-width IV: ordered graphs and matrices. CoRR, abs/2102.03117, Accepted at STOC 2022. URL: http://arxiv.org/abs/2102.03117.
  6. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: Tractable FO Model Checking. J. ACM, 69(1):1-46, November 2022. URL: https://doi.org/10.1145/3486655.
  7. Édouard Bonnet and Tillmann Miltzow. Parameterized hardness of art gallery problems. ACM Trans. Algorithms, 16(4):42:1-42:23, 2020. URL: https://doi.org/10.1145/3398684.
  8. Édouard Bonnet, Jaroslav Nesetril, 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.
  9. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  10. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 4. Springer, 2015. Google Scholar
  11. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  12. Rodney G. Downey, Michael R. Fellows, and Udayan Taylor. The parameterized complexity of relational database queries and an improved characterization of W[1]. In Douglas S. Bridges, Cristian S. Calude, Jeremy Gibbons, Steve Reeves, and Ian H. Witten, editors, First Conference of the Centre for Discrete Mathematics and Theoretical Computer Science, DMTCS 1996, Auckland, New Zealand, December, 9-13, 1996, pages 194-213. Springer-Verlag, Singapore, 1996. Google Scholar
  13. Zdenek Dvorák, Daniel Král, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. J. ACM, 60(5):36:1-36:24, 2013. URL: https://doi.org/10.1145/2499483.
  14. Zdenek Dvorák and Sergey Norin. Strongly sublinear separators and polynomial expansion. SIAM J. Discrete Math., 30(2):1095-1101, 2016. URL: https://doi.org/10.1137/15M1017569.
  15. Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi, Stephan Kreutzer, Patrice Ossona de Mendez, Michal Pilipczuk, Daniel A. Quiroz, Roman Rabinovich, and Sebastian Siebertz. Model-checking on ordered structures. ACM Trans. Comput. Log., 21(2):11:1-11:28, 2020. URL: https://doi.org/10.1145/3360011.
  16. Stephan J. Eidenbenz. Inapproximability of finding maximum hidden sets on polygons and terrains. Comput. Geom., 21(3):139-153, 2002. URL: https://doi.org/10.1016/S0925-7721(01)00029-3.
  17. Fedor V. Fomin, Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Bidimensionality. In Encyclopedia of Algorithms, pages 203-207. Springer, 2016. URL: https://doi.org/10.1007/978-1-4939-2864-4_47.
  18. Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Daniel Lokshtanov, and M. S. Ramanujan. A new perspective on FO model checking of dense graph classes. ACM Trans. Comput. Log., 21(4):28:1-28:23, 2020. URL: https://doi.org/10.1145/3383206.
  19. Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk. First-order interpretations of bounded expansion classes. ACM Trans. Comput. Log., 21(4):29:1-29:41, 2020. URL: https://doi.org/10.1145/3382093.
  20. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. J. ACM, 64(3):17:1-17:32, 2017. URL: https://doi.org/10.1145/3051095.
  21. Petr Hlinený and Filip Pokrývka, 2022. Personal communication. Google Scholar
  22. Petr Hliněnỳ, Filip Pokrỳvka, and Bodhayan Roy. FO model checking on geometric graphs. Computational Geometry, 78:1-19, 2019. Google Scholar
  23. Stephan Kreutzer and Anuj Dawar. Parameterized complexity of first-order logic. Electronic Colloquium on Computational Complexity (ECCC), 16:131, 2009. URL: http://eccc.hpi-web.de/report/2009/131, URL: http://arxiv.org/abs/TR09-131.
  24. James R. Lee. Separators in region intersection graphs. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 1:1-1:8. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.1.
  25. Bingkai Lin. The parameterized complexity of the k-biclique problem. J. ACM, 65(5):34:1-34:23, 2018. URL: https://doi.org/10.1145/3212622.
  26. Klaus-Peter Podewski and Martin Ziegler. Stable graphs. Fundamenta Mathematicae, 100(2):101-107, 1978. Google Scholar
  27. Thomas C. Shermer. Hiding people in polygons. Computing, 42(2-3):109-131, 1989. URL: https://doi.org/10.1007/BF02239742.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact