Algorithms and Complexity Seminar
Winter Term 2024/25
Seminar topic: Cops and Robber Games on Graphs
The basic cops and robber game on a graph G is defined as follows. A cop and a robber are each initially placed on a node of G. The cop and the robber make alterating moves on the graph. In each move, the cop/robber can either stay where it is or move to a neighboring node. The robber wins the game if it can avoid to ever getting caught and the cop wins the game if it manages to catch the robber (i.e., be on the same node). Variations of this basic game lead to a rich theory and there are nice connections between this game and several graph-theoretic concepts. In the seminar, we will make a tour through the results that have been published on the topic of cops and robbers games (also called pursuit-evasion games) on graphs.
Seminar description
To pass the seminar, each student participating in the seminar has to present one paper (the list of possible papers will soon be published on this webpage). The presentations about each paper will be 45 minutes (approx. 60 mins including questions) so that we have enough time to dive into the papers in sufficient detail to really understand what is going on. For the talks, we will have four meetings, each on a Friday from 12:15 - 16:00. We will have three talks in each of those meetings. Attendance to those meetings is mandatory to pass the seminar. In the first week on Thurday, 17.10.2024, at 12:15, there will be an introductory meeting to the seminar, where will explain our plan for the seminar in more detail.
Schedule
Thursday, 17.10.2024, 12:15 - 14:00: Introductory Meeting (in room 101-02-016/18)
Note that you have to sign up to the seminar through HISinOne by 21.10.2024. The process of how to sign up for seminars and how the assignment of the seminar slots is organized is decribed here.
Friday, 06.12.2024, 13:15 - 17:30: Presentations I (in room 51-00-006)
- Introduction to Cops and Robbers: Cop-win graphs, cop number, upper bound by treewidth
References: Chapter 2 (Â§2.1, Â§2.2, Â§2.3) of [Bonato]
(presented by David Stark , supervised by Zahra Parsaeian) - Cop number of planar and outerplanar graphs
References: Chapter 2 (Â§2.4) of [Bonato], Paper by Aigner and Fromme
(presented by Vincent von Bosse , supervised by Salwa Faour) - The n/exp(sqrt(log n)) upper bound on cop number
References: Chapter 2 (Â§2.5, Theorem 2.18.) of [Bonato]
(presented by Marvin Stötzel , supervised by Fabian Kuhn) - Introduction to capture time, lower bound on the capture time
References: Paper by Brandt, Emek, Uitto, and Wattenhofer
(presented by Robert Gorden , supervised by Gustav Schmid)
Friday, 13.12.2024, 13:15 - 17:30: Presentations II (in room 51-00-006)
- Graph Searching: Monotone Strategies
References: Chapter 3 (Â§3.3) of [Bonato]
(presented by Julius Fischer , supervised by Attila MÃ¡lyusz) - Graph Searching: Node Search and Pathwidth
References: Chapter 3 (Â§3.4) of [Bonato]
(presented by Arthur Diener , supervised by Zahra Parsaeian) - Helicopter Cops
References: Chapter 3 (Â§3.6) of [Bonato]
(presented by Peter Gillessen , supervised by Gustav Schmid) - Graph Burning
References: Chapter 4 (Â§4.1, Â§4.2, Â§4.3) of [Bonato], Paper by Bastide, Bonamy, Bonato, Charbit, Kamali, Pierron, and Rabie
(presented by Deniz Atalay , supervised by Marc Fuchs)
Friday, 10.01.2025, 13:15 - 17:30: Presentations III (in room 51-00-006)
- Cops and robbers in directed planar graphs
References: Paper by Loh and Oh
(presented by Max Lehr , supervised by Salwa Faour) - Characterization of k-cop win graphs
References: Paper by Clarke and MacGillivray
(presented by Jonas Friedrich , supervised by Gustav Schmid) - Angel and Devil (k = 1)
References: Chapter 8 (Â§8.5) of [Bonato], Paper by Bowditch
(presented by Frederic Frenkel , supervised by Attila MÃ¡lyusz) - Angel and Devil (k > 1)
References: Chapter 8 (Â§8.5) of [Bonato], Paper by Máthé
(presented by Lukas Kneißl , supervised by Attila MÃ¡lyusz)
Friday, 24.01.2025, 13:15 - 17:30: Presentations IV (in room 51-00-006)
- Generalized cops and robber games
References: Paper by Bonato and MacGillivray
(presented by Sebastian Klähn , supervised by Salwa Faour) - Fine-grained lower bound
References: Paper by Brandt, Pettie, and Uitto
(presented by Malte Pullich , supervised by Zahra Parsaeian) - Localization game
References: Chapter 5 of [Bonato], Paper by Suzanne Seager
(presented by Johannes Wahl , supervised by Marc Fuchs) - Firefighter game
References: Chapter 6 (Â§6.1, Â§6.2, Â§6.3) of [Bonato]
(presented by Yoshi Steinbach , supervised by Marc Fuchs)
[Bonato]
An Invitation to Pursuit-Evasion Games and
Graph Theory
Book by Anthony Bonato, published by the American Mathematical
Society (AMS).
Tentative List of Seminar Papers/Material
The seminar topics will (mostly) be chosen among the material that is covered by the following books and papers. We will soon provide an exact schedule of what should be presented when.
- An Invitation to Pursuit-Evasion Games and
Graph Theory
Book by Anthony Bonato, published by the American Mathematical Society (AMS). - Graph Searching Games and the Probabilistic Method
Book by Anthony Bonato and Paweƚ Praƚat, published by CRC Press. - A Game of Cops and Robbers
Paper by Martin Aigner and M. Fromme, Discrete Applied Mathematics 8 (1), 1984. - Cops
and Robbers From a Distance
Paper by Anthony Bonato, Ehsan Chiniforooshan, and Paweƚ Praƚat, Theoretical Computer Science 411 (43), 2010. - Cops and
Robbers on Planar-Directed Graphs
Paper by Po-Shen Loh and Siyoung Oh, Journal of Graph Theory 86 (3), 2017. - Characterizations
and Algorithms for Generalized Cops and Robbers
Games
Paper by Anthony Bonato and Gary MacGillivray, Contributions to Discrete Mathematics 12 (1), 2017. - A Tight
Lower Bound for the Capture Time of the Cops and Robbers
Game
Paper by Sebastian Brandt, Yuval Emek, Jara Uitto, and Roger Wattenhofer, Theoretical Computer Science 839, 2020. - Fine-Grained
Lower Bounds on Cops and Robbers
Paper by Sebastian Brandt, Seth Pettie, and Jara Uitto, 26th Annual European Symposium on Algorithms (ESA), 2018. - Improved
Pyrotechnics: Closer to the Burning Number Conjecture
Paper by Paul Bastide, Marthe Bonamy, Anthony Bonato, Pierre Charbit, Shahin Kamali, Théo Pierron, and Mikaël Rabie, Electronic Journal of Combinatorics 30 (4), 2020.