Zum Inhalt springen

Nur-Lesen-Fassung: Das Forschungsinformationssystem (FIS) ist aus Sicherheitsgründen vorübergehend durch diese Nur-Lesen-Fassung ersetzt. Alle öffentlichen Inhalte und Volltexte sind weiterhin abrufbar; Anmeldung, Bearbeitung, Einreichung und Statistiken stehen nicht zur Verfügung. Bei Fragen: fis@uni-bamberg.de

Start › Publikationen › Going deep and going wide : Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth

Publikation

Going deep and going wide : Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth

Adler, Isolde; Fluck, Eva; Seppelt, Tim; u. a. (2026): Going deep and going wide : Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth, in: Logical methods in computer science : LMCS, Erlangen, S. 33:1–33:48, doi: 10.46298/lmcs-22(2:33)2026.

Details

Fakultät/Lehrstuhl
Autorin(nen)/Autor(en)
Fluck, Eva
Seppelt, Tim
Spitzer, Gian Luca
Titel der Zeitschrift
Logical methods in computer science : LMCS
ISSN
1860-5974
Herausgebende Institution
Logical Methods in Computer Science e.V.
Konferenz
Annual Conference on Compuer Science Logic
Verlagsangabe
Erlangen
Erscheinungsjahr
2026
Jahrgang
22
Heft
2
Sprache(n)
Englisch
DOI
Abstract

We study the expressive power of first-order logic with counting quantifiers, especially the k-variable and quantifier-rank-q fragment, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio~(2021) proved that two graphs satisfy the same k-variable and quantifier-rank-q sentences if and only if they are homomorphism indistinguishable over the class of graphs admitting a k-pebble forest cover of depth q. After reproving this result using elementary means, we provide a graph-theoretic analysis of this graph class. This allows us to separate it from the intersection of the class of all graphs of treewidth at most k−1 and the class of all graphs of treedepth at most q, provided that q is sufficiently larger than k.

We are able to lift this separation to a (semantic) separation of the respective homomorphism indistinguishability relations. We do this by showing that the graph classes of all graphs of treedepth at most q and of graphs admitting a k-pebble forest cover of depth q are homomorphism distinguishing closed, as conjectured by Roberson~(2022).

In order to prove Roberson's conjecture for the class of graphs admitting a k-pebble forest cover of depth q we characterise the class in terms of a monotone Cops-and-Robber game.The crux is to prove that if Cop has a winning strategy then Cop also has a winning strategy that is monotone.To that end, we show how to transform Cop's winning strategy into a pre-tree-decomposition, which is inspired by decompositions of matroids, and then applying an intricate breadth-first `cleaning up' procedure along the pre-tree-decomposition (which may temporarily lose the property of representing a strategy), in order to achieve monotonicity while controlling the number of rounds simultaneously across all branches of the decomposition via a vertex exchange argument.

Freie Schlagwort(e)
Logic in Computer Science
Discrete Mathematics
Combinatorics
Dokumenttyp
Konferenzveröffentlichung
URI
Datum der Freischaltung
01.07.2026

Permalink: https://fis.uni-bamberg.de/handle/uniba/115889 · Daten als JSON · Zitieren: BibTeX · RIS

Datenstand: 15.11.2026

Eingeschränkter Lesezugriff: Anmeldung, Bearbeitung und Einreichung sind vorübergehend deaktiviert.