2026-07-21T23:52:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23544 2025-10-02T12:58:20Z ddc:004 open_access

Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO Mählmann, Nikolas Shrub-Depth Forbidden Induced Subgraphs MSO Stability Theory The graph parameter shrub-depth is a dense analog of tree-depth. We characterize classes of bounded shrub-depth by forbidden induced subgraphs. The obstructions are well-controlled flips of large half-graphs and of disjoint unions of many long paths. Applying this characterization, we show that on every hereditary class of unbounded shrub-depth, MSO is more expressive than FO. This confirms a conjecture of [Gajarský and Hliněný; LMCS 2015] who proved that on classes of bounded shrub-depth FO and MSO have the same expressive power. Combined, the two results fully characterize the hereditary classes on which FO and MSO coincide, answering an open question by [Elberfeld, Grohe, and Tantau; LICS 2012]. Our work is inspired by the notion of stability from model theory. A graph class 𝒞 is MSO-stable, if no MSO-formula can define arbitrarily long linear orders in graphs from 𝒞. We show that a hereditary graph class is MSO-stable if and only if it has bounded shrub-depth. As a key ingredient, we prove that every hereditary class of unbounded shrub-depth FO-interprets the class of all paths. This improves upon a result of [Ossona de Mendez, Pilipczuk, and Siebertz; Eur. J. Comb. 2025] who showed the same statement for FO-transductions instead of FO-interpretations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikolas Mählmann 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.167 urn:nbn:de:0030-drops-235444 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.167 eng https://creativecommons.org/licenses/by/4.0/legalcode