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 › Monotonicity of the Cops and Robber Game for Bounded Depth Treewidth

Publikation

Monotonicity of the Cops and Robber Game for Bounded Depth Treewidth

Adler, Isolde; Fluck, Eva (2024): Monotonicity of the Cops and Robber Game for Bounded Depth Treewidth, in: Ithaca, NY: arXiv, S. 1–18, doi: 10.48550/arXiv.2402.09139.

Details

Fakultät/Lehrstuhl
Autorin(nen)/Autor(en)
Fluck, Eva
Konferenz
49th International Symposium on Mathematical Foundations of Computer Science : (MFCS 2024), August 26-30, 2024, Bratislava, Slovakia
Verlagsangabe
arXiv : Ithaca, NY
Erscheinungsjahr
2024
Sprache(n)
Englisch
DOI
Abstract

We study a variation of the cops and robber game characterising treewidth, where in each play at most q cops can be placed in order to catch the robber, where q is a parameter of the game. We prove that if k cops have a winning strategy in this game, then k cops have a monotone winning strategy. As a corollary we obtain a new characterisation of bounded depth treewidth, and we give a positive answer to an open question by Fluck, Seppelt and Spitzer (2024), thus showing that graph classes of bounded depth treewidth are homomorphism distinguishing closed. Our proof of monotonicity substantially reorganises a winning strategy by first transforming it into a pre-decomposition, which is inspired by decompositions of matroids, and then applying an intricate breadth-first ‘cleaning up’ procedure along the pre-decomposition (which may temporarily lose the property of representing a strategy), in order to achieve monotonicity while controlling the number of cop placements simultaneously across all branches of the decomposition via a vertex exchange argument. We believe this can be useful in future research.

Freie Schlagwort(e)
tree decompositions
treewidth
treedepth
cops-and-robber game
monotonicity
homomorphism distinguishing closure
Dokumenttyp
Konferenzveröffentlichung
URI
Datum der Freischaltung
28.04.2025

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

Datenstand: 15.11.2026

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