2026-07-27T05:06:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16464 2024-03-06T10:57:33Z ddc:004 open_access

Twin-Width and Types Gajarský, Jakub Pilipczuk, Michał Przybyszewski, Wojciech Toruńczyk, Szymon twin-width FO logic model checking query answering enumeration We study problems connected to first-order logic in graphs of bounded twin-width. Inspired by the approach of Bonnet et al. [FOCS 2020], we introduce a robust methodology of local types and describe their behavior in contraction sequences - the decomposition notion underlying twin-width. We showcase the applicability of the methodology by proving the following two algorithmic results. In both statements, we fix a first-order formula φ(x_1,…,x_k) and a constant d, and we assume that on input we are given a graph G together with a contraction sequence of width at most d. - One can in time 𝒪(n) construct a data structure that can answer the following queries in time 𝒪(log log n): given w_1,…,w_k, decide whether φ(w_1,…,w_k) holds in G. - After 𝒪(n)-time preprocessing, one can enumerate all tuples w₁,…,w_k that satisfy φ(x_1,…,x_k) in G with 𝒪(1) delay. In the first case, the query time can be reduced to 𝒪(1/ε) at the expense of increasing the construction time to 𝒪(n^{1+ε}), for any fixed ε > 0. Finally, we also apply our tools to prove the following statement, which shows optimal bounds on the VC density of set systems that are first-order definable in graphs of bounded twin-width. - Let G be a graph of twin-width d, A be a subset of vertices of G, and φ(x_1,…,x_k,y_1,…,y_l) be a first-order formula. Then the number of different subsets of A^k definable by φ using l-tuples of vertices from G as parameters, is bounded by O(|A|^l). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakub Gajarský and Michał Pilipczuk and Wojciech Przybyszewski and Szymon Toruńczyk 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.123 urn:nbn:de:0030-drops-164640 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.123 eng https://creativecommons.org/licenses/by/4.0/legalcode