License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.123
URN: urn:nbn:de:0030-drops-164640
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16464/
Gajarský, Jakub ;
Pilipczuk, Michał ;
Przybyszewski, Wojciech ;
Toruńczyk, Szymon
Twin-Width and Types
Abstract
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).
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 = {{Twin-Width and Types}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {123:1--123:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16464},
URN = {urn:nbn:de:0030-drops-164640},
doi = {10.4230/LIPIcs.ICALP.2022.123},
annote = {Keywords: twin-width, FO logic, model checking, query answering, enumeration}
}
|
Keywords: |
|
twin-width, 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 |
