2026-07-22T11:19:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18187 2024-03-06T11:01:15Z ddc:004 open_access

Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes Ohlmann, Pierre Pilipczuk, Michał Przybyszewski, Wojciech Toruńczyk, Szymon Model Theory Stability Theory Shrubdepth Nowhere Dense Monadically Stable 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pierre Ohlmann and Michał Pilipczuk and Wojciech Przybyszewski and Szymon Toruńczyk 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.135 urn:nbn:de:0030-drops-181874 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.135 eng https://creativecommons.org/licenses/by/4.0/legalcode