Uni-Logo
Algorithms and Complexity
 

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)

  1. 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)
  2. 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)
  3. 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 Attila Mályusz)
  4. Introduction to capture time, lower bound on the capture time
    References: Paper by Brandt, Emek, Uitto, and Wattenhofer
    (presented by Robert Gorden , supervised by Fabian Kuhn)

Friday, 13.12.2024, 13:15 - 17:30: Presentations II (in room 51-00-006)

  1. Graph Searching: Monotone Strategies
    References: Chapter 3 (§3.3) of [Bonato]
    (presented by Julius Fischer , supervised by Gustav Schmid)
  2. Graph Searching: Node Search and Pathwidth
    References: Chapter 3 (§3.4) of [Bonato]
    (presented by Arthur Diener , supervised by Zahra Parsaeian)
  3. Helicopter Cops
    References: Chapter 3 (§3.6) of [Bonato]
    (presented by Peter Gillessen , supervised by Gustav Schmid)
  4. 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)

  1. Cops and robbers in directed planar graphs
    References: Paper by Loh and Oh
    (presented by Max Lehr , supervised by Salwa Faour)
  2. Characterization of k-cop win graphs
    References: Paper by Clarke and MacGillivray
    (presented by Jonas Friedrich , supervised by Gustav Schmid)
  3. Angel and Devil (k = 1)
    References: Chapter 8 (§8.5) of [Bonato], Paper by Bowditch
    (presented by Frederic Frenkel , supervised by Attila Mályusz)
  4. 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)

  1. Generalized cops and robber games
    References: Paper by Bonato and MacGillivray
    (presented by Sebastian Klähn , supervised by Salwa Faour)
  2. Fine-grained lower bound
    References: Paper by Brandt, Pettie, and Uitto
    (presented by Malte Pullich , supervised by Zahra Parsaeian)
  3. Localization game
    References: Chapter 5 of [Bonato], Paper by Suzanne Seager
    (presented by Johannes Wahl , supervised by Marc Fuchs)
  4. 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.