Decomposition horizons: from graph sparsity to model-theoretic dividing lines

EUROCOMB’23

Sam Braunfeld Jaroslav Nešetřil Patrice Ossona de Mendez Sebastian Siebertz

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-030

PDF
Abstract
Low treedepth decompositions are central to the structural characterizations of bounded expansion classes and nowhere dense classes, and the core of main algorithmic properties of these classes, including fixed-parameter (quasi) linear-time algorithms checking whether a fixed graph $F$ is an induced subgraph of the input graph $G$. These decompositions have been extended to structurally bounded expansion classes and structurally nowhere dense classes, where low treedepth decompositions are replaced by low shrubdepth decompositions. In the emerging framework of a structural graph theory for hereditary classes of structures based on tools from model theory, it is natural to ask how these decompositions behave with the fundamental model theoretical notions of dependence (alias NIP) and stability. In this work, we prove that the model theoretical notions of NIP and stable classes are transported by decompositions. Precisely: Let $\mathscr C$ be a hereditary class of graphs. Assume that for every $p$ there is a hereditary NIP class $\mathscr D_p$ with the property that the vertex set of every graph $G\in\mathscr C$ can be partitioned into $N_p=N_p(G)$ parts in such a way that the union of any $p$ parts induce a subgraph in $\mathscr D_p$ and $\log N_p(G)\in o(\log |G|)$. We prove that then $\mathscr C$ is (monadically) NIP. Similarly, if every $\mathscr D_p$ is stable, then $\mathscr C$ is (monadically) stable. Results of this type lead to the definition of decomposition horizons as closure operators. We establish some of their basic properties and provide several further examples of decomposition horizons.

Pages:
216–222
References

Adler, H. & Adler, I. (2014) Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics, 36, 322-330.
https://doi.org/10.1016/j.ejc.2013.06.048

Baker, B.S. (1994) Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41, 153-180.
https://doi.org/10.1145/174644.174650

Baldwin, J.T. & Shelah, S. (1985) Second-order quantifiers and the complexity of theories. Notre Dame Journal of Formal Logic, 26, 229-303.
https://doi.org/10.1305/ndjfl/1093870870

Bonnet, E., Giocanti, U., Ossona de Mendez, P., Simon, P., Thomassé, S., & Toruńczyk, S. (2022) Twin-width IV: ordered graphs and matrices. STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing.
https://doi.org/10.1145/3519935.3520037

Braunfeld, S. & Laskowski, M.C. (2022) Existential characterizations of monadic NIP. arXiv preprint arXiv:2209.05120.

Braunfeld, S., Nešetřil, J., Ossona de Mendez, P., & Siebertz, S. (2022) On the first-order transduction quasiorder of hereditary classes of graphs. arXiv preprint arXiv:2208.14412.

DeVos, M., Ding, G., Oporowski, B., Sanders, D.P., Reed, B., Seymour, P.D., & Vertigan, D. (2004) Excluding any graph as a minor allows a low tree-width 2-coloring. Journal of Combinatorial Theory, Series B, 91, 25-41.
https://doi.org/10.1016/j.jctb.2003.09.001

Dreier, J., Gajarský, J., Kiefer, S., Pilipczuk, M., & Toruńczyk, S. (2022) Treelike decompositions for transductions of sparse graphs. arXiv preprint arXiv:2201.11082.
https://doi.org/10.1145/3531130.3533349

Gajarský, J., Hliněný, P., Obdržálek, J., Lokshtanov, D., & Ramanujan, M.S. (2016) A New Perspective on FO Model Checking of Dense Graph Classes. Proceedings of the Thirty-First Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). ACM, pp. 176-184.
https://doi.org/10.1145/2933575.2935314

Gajarský, J., Kreutzer, S., Nešetřil, J., Ossona de Mendez, P., Pilipczuk, M., Siebertz, S., & Toruńczyk, S. (2018) First-order interpretations of bounded expansion classes. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), vol. 107, Leibniz International Proceedings in Informatics (LIPIcs). pp. 126:1-126:14.

Ganian, R., Hliněný, P., Nešetřil, J., Obdržálek, J., & Ossona de Mendez, P. (2019) Shrub-depth: Capturing Height of Dense Graphs. Logical Methods in Computer Science, 15.

Ganian, R., Hliněnỳ, P., Nešetřil, J., Obdržálek, J., Mendez, P.O. de, & Ramadurai, R. (2012) When trees grow low: shrubs and fast MSO1 . International Symposium on Mathematical Foundations of Computer Science. Springer, pp. 419-430.
https://doi.org/10.1007/978-3-642-32589-2_38

Kwon, O.-j., Pilipczuk, M., & Siebertz, S. (2017) On low rank-width colorings. Graph-theoretic concepts in computer science, vol. 10520, Lecture Notes in Comput. Sci. Springer, Cham, pp. 372-385.
https://doi.org/10.1007/978-3-319-68705-6_28

Laskowski, M.C. (2013) Mutually algebraic structures and expansions by predicates. The Journal of Symbolic Logic, 78, 185-194.
https://doi.org/10.2178/jsl.7801120

Nešetřil, J. & Ossona de Mendez, P. (2008) Grad and Classes with Bounded Expansion I. Decompositions. European Journal of Combinatorics, 29, 760-776.
https://doi.org/10.1016/j.ejc.2006.07.013

Nešetřil, J. & Ossona de Mendez, P. (2012) Sparsity (Graphs, Structures, and Algorithms), vol. 28, Algorithms et Combinatorics. Springer.
https://doi.org/10.1007/978-3-642-27875-4

Nešetřil, J. & Ossona de Mendez, P. (2015) On Low Tree-Depth Decompositions. Graphs and Combinatorics, 31, 1941-1963.
https://doi.org/10.1007/s00373-015-1569-7

Nešetřil, J. & Ossona de Mendez, P. (2016) Structural Sparsity. Uspekhi Matematicheskikh Nauk, 71, 85-116.
https://doi.org/10.1070/RM9688

Nešetřil, J., Ossona de Mendez, P., Pilipczuk, M., Rabinovich, R., & Siebertz, S. (2021) Rankwidth meets stability. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 2014-2033.
https://doi.org/10.1137/1.9781611976465.120

Nešetřil, J., Ossona de Mendez, P., Rabinovich, R., & Siebertz, S. (2020) Linear rankwidth meets stability. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (Chawla, S. ed). pp. 1180-1199.
https://doi.org/10.1137/1.9781611975994.72

Shelah, S. (1990) Classification theory: and the number of non-isomorphic models, vol. 92. Elsevier.

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Sam Braunfeld, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz

PDF