Document Open Access Logo

Flipper Games for Monadically Stable Graph Classes

Authors Jakub Gajarský , Nikolas Mählmann , Rose McCarty , Pierre Ohlmann , Michał Pilipczuk , Wojciech Przybyszewski , Sebastian Siebertz , Marek Sokołowski , Szymon Toruńczyk

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.128.pdf
  • Filesize: 0.87 MB
  • 16 pages

Document Identifiers

Author Details

Jakub Gajarský
  • University of Warsaw, Poland
Nikolas Mählmann
  • Universität Bremen, Germany
Rose McCarty
  • Princeton University, NJ, USA
Pierre Ohlmann
  • University of Warsaw, Poland
Michał Pilipczuk
  • University of Warsaw, Poland
Wojciech Przybyszewski
  • University of Warsaw, Poland
Sebastian Siebertz
  • Universität Bremen, Germany
Marek Sokołowski
  • University of Warsaw, Poland
Szymon Toruńczyk
  • University of Warsaw, Poland

Funding

This work is a part of projects CUTACOMBS (R. McCarty) and BOBR (J. Gajarsk{ý}, P. Ohlmann, M. Pilipczuk, W. Przybyszewski, M. Sokołowski and S. Toruńczyk) that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreements No. 714704 and 948057, respectively). Nikolas Mählmann and Sebastian Siebertz are supported by the German Research Foundation (DFG) with grant agreement No. 444419611. Rose McCarty is also supported by National Science Foundation (NSF) grant No DMS-2202961.

Cite As Get BibTex

Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski, and Szymon Toruńczyk. Flipper Games for Monadically Stable Graph Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 128:1-128:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.128

Abstract

A class of graphs C is monadically stable if for every unary expansion Ĉ of C, one cannot encode - using first-order transductions - arbitrarily long linear orders in graphs from C. It is known that nowhere dense graph classes are monadically stable; these include classes of bounded maximum degree and classes that exclude a fixed topological minor. On the other hand, monadic stability is a property expressed in purely model-theoretic terms that is also suited for capturing structure in dense graphs.
In this work we provide a characterization of monadic stability in terms of the Flipper game: a game on a graph played by Flipper, who in each round can complement the edge relation between any pair of vertex subsets, and Localizer, who in each round is forced to restrict the game to a ball of bounded radius. This is an analog of the Splitter game, which characterizes nowhere dense classes of graphs (Grohe, Kreutzer, and Siebertz, J. ACM '17). 
We give two different proofs of our main result. The first proof is based on tools borrowed from model theory, and it exposes an additional property of monadically stable graph classes that is close in spirit to definability of types. Also, as a byproduct, we show that monadic stability for graph classes coincides with monadic stability of existential formulas with two free variables, and we provide another combinatorial characterization of monadic stability via forbidden patterns. The second proof relies on the recently introduced notion of flip-flatness (Dreier, Mählmann, Siebertz, and Toruńczyk, arXiv 2206.13765) and provides an efficient algorithm to compute Flipper’s moves in a winning strategy.

Subject Classification

ACM Subject Classification
  • Theory of computation → Finite Model Theory
  • Mathematics of computing → Graph theory
Keywords
  • Stability theory
  • structural graph theory
  • games

Metrics

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

Related Versions

References

  1. Algorithms, Logic and Structure Workshop in Warwick - Open Problem Session. URL: https://warwick.ac.uk/fac/sci/maths/people/staff/daniel_kral/alglogstr/openproblems.pdf, 2016. [Online; accessed 23-Jan-2023].
  2. Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. Eur. J. Comb., 36:322-330, 2014. URL: https://doi.org/10.1016/j.ejc.2013.06.048.
  3. J.T. Baldwin and S. Shelah. Second-order quantifiers and the complexity of theories. Notre Dame Journal of Formal Logic, 26(3):229-303, 1985. Google Scholar
  4. Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk. Twin-width iv: Ordered graphs and matrices. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 924-937, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3519935.3520037.
  5. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. In Sandy Irani, editor, 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.
  6. Samuel Braunfeld and Michael C Laskowski. Existential characterizations of monadic NIP. arXiv preprint, 2022. URL: https://arxiv.org/abs/2209.05120.
  7. Anuj Dawar. Homomorphism preservation on quasi-wide classes. J. Comput. Syst. Sci., 76(5):324-332, 2010. URL: https://doi.org/10.1016/j.jcss.2009.10.005.
  8. Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz. First-order model checking on structurally sparse graph classes. arXiv preprint, 2023. URL: https://arxiv.org/abs/2302.03527.
  9. Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, and Szymon Toruńczyk. Indiscernibles and flatness in monadically stable and monadically NIP classes. arXiv preprint, 2022. URL: https://arxiv.org/abs/2206.13765.
  10. Zdenek Dvořák. Induced subdivisions and bounded expansion. Eur. J. Comb., 69:143-148, 2018. URL: https://doi.org/10.1016/j.ejc.2017.10.004.
  11. Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski, and Szymon Toruńczyk. Flipper games for monadically stable graph classes, 2023. URL: https://doi.org/10.48550/ARXIV.2301.13735.
  12. Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek, and Patrice Ossona de Mendez. Shrub-depth: Capturing height of dense graphs. Log. Methods Comput. Sci., 15(1), 2019. URL: https://doi.org/10.23638/LMCS-15(1:7)2019.
  13. Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek, Patrice Ossona de Mendez, and Reshma Ramadurai. When trees grow low: Shrubs and fast MSO₁. In 37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012, volume 7464 of Lecture Notes in Computer Science, pages 419-430. Springer, 2012. Google Scholar
  14. 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.
  15. Jaroslav Nešetřil and Patrice Ossona de Mendez. On nowhere dense graphs. Eur. J. Comb., 32(4):600-617, 2011. URL: https://doi.org/10.1016/j.ejc.2011.01.006.
  16. Klaus-Peter Podewski and Martin Ziegler. Stable graphs. Fundamenta Mathematicae, 100(2):101-107, 1978. Google Scholar
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 About DROPS Imprint Privacy Contact