Abstract
We study problems connected to firstorder logic in graphs of bounded twinwidth. 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 twinwidth. We showcase the applicability of the methodology by proving the following two algorithmic results. In both statements, we fix a firstorder 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 firstorder definable in graphs of bounded twinwidth.
 Let G be a graph of twinwidth d, A be a subset of vertices of G, and φ(x_1,…,x_k,y_1,…,y_l) be a firstorder formula. Then the number of different subsets of A^k definable by φ using ltuples of vertices from G as parameters, is bounded by O(A^l).
BibTeX  Entry
@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2022.123,
author = {Gajarsk\'{y}, Jakub and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Toru\'{n}czyk, Szymon},
title = {{TwinWidth and Types}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {123:1123:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16464},
URN = {urn:nbn:de:0030drops164640},
doi = {10.4230/LIPIcs.ICALP.2022.123},
annote = {Keywords: twinwidth, FO logic, model checking, query answering, enumeration}
}
Keywords: 

twinwidth, FO logic, model checking, query answering, enumeration 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 