Evaluating First-Order Formulas in Structured Graphs (Invited Talk)

Toruńczyk, Szymon

doi:10.4230/LIPIcs.ICDT.2025.3

Evaluating First-Order Formulas in Structured Graphs

Szymon Toruńczyk

University of Warsaw, Poland

Abstract

A central problem in database theory concerns the complexity of the query evaluation problem, also called the model-checking problem in finite model theory: the problem of evaluating a given formula in a given structure. Here, I will focus on formulas of first-order logic, and the data complexity (or parameterized complexity) of their evaluation. Leveraging tools from structural graph theory, I will assume that the input structure is a graph which comes from a fixed class of well-structured graphs, such as the class of planar graphs, classes of bounded treewidth or clique-width, or much more general “tame” graph classes, such as the nowhere dense graph classes introduced by Ossona de Mendez and Nešetřil, or classes of bounded twin-width studied by Bonnet, Thomassé, and coauthors.

I will survey the recent progress in this area, which connects tools from structural graph theory, from model theory – such as stability and dependence – and from statistical learning theory and computational geometry – such as VC-dimension and $\varepsilon$ -nets.

Keywords and phrases:

Finite model theory, first-order model checking, graph parameters

Category:

Invited Talk

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Finite Model Theory ; Mathematics of computing

\rightarrow

Graph theory

Funding:

^†^†margin:

S.T. is supported by the project BUKA that is funded from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme with grant agreement No. 101126229.

DOI:

10.4230/LIPIcs.ICDT.2025.3

Event:

28th International Conference on Database Theory (ICDT 2025)

Editors:

Sudeepa Roy and Ahmet Kara

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

References

[1] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: Tractable fo model checking. J. ACM, 69(1), November 2021. doi:10.1145/3486655.
[2] Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michał Pilipczuk, and Szymon Toruńczyk. First-order model checking on monadically stable graph classes. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024. IEEE, 2024. doi:10.1109/FOCS61266.2024.00012.
[3] Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz. First-order model checking on structurally sparse graph classes. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 567–580. ACM, 2023. doi:10.1145/3564246.3585186.
[4] Jan Dreier, Nikolas Mählmann, and Szymon Toruńczyk. Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1550–1560. ACM, 2024. doi:10.1145/3618260.3649739.
[5] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. J. ACM, 64(3):17:1–17:32, 2017. doi:10.1145/3051095.
[6] Jaroslav Nešetřil and Patrice Ossona de Mendez. On nowhere dense graphs. Eur. J. Comb., 32(4):600–617, 2011. doi:10.1016/j.ejc.2011.01.006.
[7] Szymon Toruńczyk. Flip-width: Cops and robber on dense graphs. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 663–700. IEEE, 2023. doi:10.1109/FOCS57990.2023.00045.

[bib.bib1] [1] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: Tractable fo model checking. J. ACM, 69(1), November 2021. doi:10.1145/3486655.

[bib.bib2] [2] Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michał Pilipczuk, and Szymon Toruńczyk. First-order model checking on monadically stable graph classes. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024. IEEE, 2024. doi:10.1109/FOCS61266.2024.00012.

[bib.bib3] [3] Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz. First-order model checking on structurally sparse graph classes. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 567–580. ACM, 2023. doi:10.1145/3564246.3585186.

[bib.bib4] [4] Jan Dreier, Nikolas Mählmann, and Szymon Toruńczyk. Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1550–1560. ACM, 2024. doi:10.1145/3618260.3649739.

[bib.bib5] [5] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. J. ACM, 64(3):17:1–17:32, 2017. doi:10.1145/3051095.

[bib.bib6] [6] Jaroslav Nešetřil and Patrice Ossona de Mendez. On nowhere dense graphs. Eur. J. Comb., 32(4):600–617, 2011. doi:10.1016/j.ejc.2011.01.006.

[bib.bib7] [7] Szymon Toruńczyk. Flip-width: Cops and robber on dense graphs. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 663–700. IEEE, 2023. doi:10.1109/FOCS57990.2023.00045.