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.2023.135
URN: urn:nbn:de:0030-drops-181874
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18187/
Ohlmann, Pierre ;
Pilipczuk, Michał ;
Przybyszewski, Wojciech ;
Toruńczyk, Szymon
Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes
Abstract
We use model-theoretic tools originating from stability theory to derive a result we call the Finitary Substitute Lemma, which intuitively says the following. Suppose we work in a stable graph class ?, and using a first-order formula φ with parameters we are able to define, in every graph G ∈ ?, a relation R that satisfies some hereditary first-order assertion ψ. Then we are able to find a first-order formula φ' that has the same property, but additionally is finitary: there is finite bound k ∈ ℕ such that in every graph G ∈ ?, different choices of parameters give only at most k different relations R that can be defined using φ'.
We use the Finitary Substitute Lemma to derive two corollaries about the existence of certain canonical decompositions in classes of well-structured graphs.
- We prove that in the Splitter game, which characterizes nowhere dense graph classes, and in the Flipper game, which characterizes monadically stable graph classes, there is a winning strategy for Splitter, respectively Flipper, that can be defined in first-order logic from the game history. Thus, the strategy is canonical.
- We show that for any fixed graph class ? of bounded shrubdepth, there is an ?(n²)-time algorithm that given an n-vertex graph G ∈ ?, computes in an isomorphism-invariant way a structure H of bounded treedepth in which G can be interpreted. A corollary of this result is an ?(n²)-time isomorphism test and canonization algorithm for any fixed class of bounded shrubdepth.
BibTeX - Entry
@InProceedings{ohlmann_et_al:LIPIcs.ICALP.2023.135,
author = {Ohlmann, Pierre and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Toru\'{n}czyk, Szymon},
title = {{Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {135:1--135:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18187},
URN = {urn:nbn:de:0030-drops-181874},
doi = {10.4230/LIPIcs.ICALP.2023.135},
annote = {Keywords: Model Theory, Stability Theory, Shrubdepth, Nowhere Dense, Monadically Stable}
}
|
Keywords: |
|
Model Theory, Stability Theory, Shrubdepth, Nowhere Dense, Monadically Stable |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
