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: https://drops.dagstuhl.de/opus/volltexte/2023/18187/
Go to the corresponding LIPIcs Volume Portal

Ohlmann, Pierre ; Pilipczuk, Michaล‚ ; Przybyszewski, Wojciech ; Toruล„czyk, Szymon

Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes

pdf-format:
LIPIcs-ICALP-2023-135.pdf (0.9 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI