2026-07-21T19:38:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22944 2025-10-02T12:19:19Z ddc:004 open_access

Evaluating First-Order Formulas in Structured Graphs (Invited Talk) Toruńczyk, Szymon Finite model theory first-order model checking graph parameters 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 ε-nets. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Szymon Toruńczyk 2025 Is Part Of LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2025.3 urn:nbn:de:0030-drops-229449 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.3 eng https://creativecommons.org/licenses/by/4.0/legalcode