Combinatorial and Algorithmic Aspects of Monadic Stability

Authors Jan Dreier , Nikolas Mählmann , Amer E. Mouawad , Sebastian Siebertz , Alexandre Vigny



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.11.pdf
  • Filesize: 0.84 MB
  • 17 pages

Document Identifiers

Author Details

Jan Dreier
  • TU Wien, Austria
Nikolas Mählmann
  • Universität Bremen, Germany
Amer E. Mouawad
  • American University of Beirut, Lebanon
  • Universität Bremen, Germany
Sebastian Siebertz
  • Universität Bremen, Germany
Alexandre Vigny
  • Universität Bremen, Germany

Cite AsGet BibTex

Jan Dreier, Nikolas Mählmann, Amer E. Mouawad, Sebastian Siebertz, and Alexandre Vigny. Combinatorial and Algorithmic Aspects of Monadic Stability. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.11

Abstract

Nowhere dense classes of graphs are classes of sparse graphs with rich structural and algorithmic properties, however, they fail to capture even simple classes of dense graphs. Monadically stable classes, originating from model theory, generalize nowhere dense classes and close them under transductions, i.e. transformations defined by colorings and simple first-order interpretations. In this work we aim to extend some combinatorial and algorithmic properties of nowhere dense classes to monadically stable classes of finite graphs. We prove the following results. - For every monadically stable class C and fixed integer s ≥ 3, the Ramsey numbers R_C(s,t) are bounded from above by 𝒪(t^{s-1-δ}) for some δ > 0, improving the bound R(s,t) ∈ 𝒪(t^{s-1}/(log t)^{s-1}) known for the class of all graphs and the bounds known for k-stable graphs when s ≤ k. - For every monadically stable class C and every integer r, there exists δ > 0 such that every graph G ∈ C that contains an r-subdivision of the biclique K_{t,t} as a subgraph also contains K_{t^δ,t^δ} as a subgraph. This generalizes earlier results for nowhere dense graph classes. - We obtain a stronger regularity lemma for monadically stable classes of graphs. - Finally, we show that we can compute polynomial kernels for the independent set and dominating set problems in powers of nowhere dense classes. Formerly, only fixed-parameter tractable algorithms were known for these problems on powers of nowhere dense classes.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
  • Theory of computation → Logic
Keywords
  • Monadic Stability
  • Structural Graph Theory
  • Ramsey Numbers
  • Regularity
  • Kernels

Metrics

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

References

  1. Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics, 36:322-330, 2014. Google Scholar
  2. Miklós Ajtai, János Komlós, and Endre Szemerédi. A note on ramsey numbers. Journal of Combinatorial Theory, Series A, 29(3):354-360, 1980. Google Scholar
  3. Noga Alon, Richard A Duke, Hanno Lefmann, Vojtěch Rödl, and Raphael Yuster. The algorithmic aspects of the regularity lemma. Journal of Algorithms, 16(1):80-109, 1994. Google Scholar
  4. 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
  5. Achim Blumensath. Simple monadic theories and indiscernibles. Mathematical Logic Quarterly, 57(1):65-86, 2011. URL: https://doi.org/10.1002/malq.200910121.
  6. Anuj Dawar and Stephan Kreutzer. Domination problems in nowhere-dense classes. In FSTTCS, volume 4 of LIPIcs, pages 157-168. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009. Google Scholar
  7. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  8. Rod G Downey and Michael R Fellows. Fixed-parameter tractability and completeness ii: On completeness for w [1]. Theoretical Computer Science, 141(1-2):109-131, 1995. Google Scholar
  9. Jan Dreier, Jakub Gajarskỳ, Sandra Kiefer, Michał Pilipczuk, and Szymon Toruńczyk. Treelike decompositions for transductions of sparse graphs. arXiv preprint, 2022. URL: http://arxiv.org/abs/2201.11082.
  10. Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, and Szymon Toruńczyk. Indiscernibles and wideness in monadically stable and monadically NIP classes. arXiv preprint, 2022. URL: http://arxiv.org/abs/2206.13765.
  11. Zdeněk Dvořák. Induced subdivisions and bounded expansion. European Journal of Combinatorics, 69:143-148, 2018. Google Scholar
  12. Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In ICALP, volume 80 of LIPIcs, pages 63:1-63:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  13. Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk. Progressive Algorithms for Domination and Independence. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:16, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.27.
  14. Jakub Gajarskỳ, Petr Hliněnỳ, Jan Obdržálek, Daniel Lokshtanov, and MS Ramanujan. A new perspective on fo model checking of dense graph classes. ACM Transactions on Computational Logic (TOCL), 21(4):1-23, 2020. Google Scholar
  15. Jakub Gajarskỳ, Stephan Kreutzer, Jaroslav Nešetřil, Patrice Ossona De Mendez, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. First-order interpretations of bounded expansion classes. ACM Transactions on Computational Logic (TOCL), 21(4):1-41, 2020. Google Scholar
  16. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. Journal of the ACM (JACM), 64(3):1-32, 2017. Google Scholar
  17. Wilfrid Hodges. A Shorter Model Theory. Cambridge University Press, 1997. Google Scholar
  18. Yiting Jiang, Jaroslav Nešetřil, Patrice Ossona de Mendez, and Sebastian Siebertz. Regular partitions of gentle graphs. Acta Mathematica Hungarica, 161(2):719-755, 2020. Google Scholar
  19. Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz. Polynomial kernels and wideness properties of nowhere dense graph classes. ACM Transactions on Algorithms (TALG), 15(2):1-19, 2018. Google Scholar
  20. M. Malliaris and S. Shelah. Regularity lemmas for stable graphs. Transactions of the American Mathematical Society, 366(3):1551-1585, 2014. URL: http://www.jstor.org/stable/23813167.
  21. Jaroslav Nešetřil and P Ossona de Mendez. Structural sparsity. Russian Mathematical Surveys, 71(1):79, 2016. Google Scholar
  22. Jaroslav Nešetřil and Patrice Ossona De Mendez. On nowhere dense graphs. European Journal of Combinatorics, 32(4):600-617, 2011. Google Scholar
  23. Jaroslav Nešetřil and Patrice Ossona De Mendez. Sparsity: graphs, structures, and algorithms, volume 28. Springer Science & Business Media, 2012. Google Scholar
  24. Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Rankwidth meets stability. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2014-2033. SIAM, 2021. Google Scholar
  25. Jaroslav Nešetřil, Patrice Ossona de Mendez, and Sebastian Siebertz. Structural properties of the first-order transduction quasiorder. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. Google Scholar
  26. Jaroslav Nešetřil, Roman Rabinovich, Patrice Ossona de Mendez, and Sebastian Siebertz. Linear rankwidth meets stability. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1180-1199. SIAM, 2020. Google Scholar
  27. Bejamin Oye. Stable graphs. Google Scholar
  28. Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145-147, 1972. Google Scholar
  29. Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247-261, 1972. Google Scholar
  30. Endre Szemerédi. Regular partitions of graphs. Colloq. Int. CNRS, 260:399-401, 1978. Google Scholar
  31. Vladimir Naumovitch Vapnik and Alexeï Iakovlevitch Červonenkis. On the uniform convergence of relative sequences of events to their probabilities. Theory Probab. Appl., 16:264-280, 1971. 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