Academic Journal
Monotonicity of the Cops and Robber Game for Bounded Depth Treewidth
| العنوان: | Monotonicity of the Cops and Robber Game for Bounded Depth Treewidth |
|---|---|
| المؤلفون: | Adler, Isolde, Fluck, Eva |
| المساهمون: | Isolde Adler and Eva Fluck |
| بيانات النشر: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| سنة النشر: | 2024 |
| المجموعة: | DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| مصطلحات موضوعية: | tree decompositions, treewidth, treedepth, cops-and-robber game, monotonicity, homomorphism distinguishing closure |
| الوصف: | We study a variation of the cops and robber game characterising treewidth, where in each round at most one cop may be placed and in each play at most q rounds are played, 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-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. We believe this can be useful in future research. |
| نوع الوثيقة: | article in journal/newspaper conference object |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.6 |
| DOI: | 10.4230/LIPIcs.MFCS.2024.6 |
| الاتاحة: | https://doi.org/10.4230/LIPIcs.MFCS.2024.6 https://nbn-resolving.org/urn:nbn:de:0030-drops-205621 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.6 |
| Rights: | https://creativecommons.org/licenses/by/4.0/legalcode |
| رقم الانضمام: | edsbas.A73DB23D |
| قاعدة البيانات: | BASE |
| DOI: | 10.4230/LIPIcs.MFCS.2024.6 |
|---|