Replacing Cops with Zombies

Read full text
Authors: Liu, Fengyi, Miller, Avery
Cited by: 0

Abstract

In the Cops and Robbers game, two players take turns to move their pieces in a given graph, and the goal of the Cop player is to have any of their pieces capture the piece controlled by the Robber player. In the Zombies and Survivors variant, the Zombie player is trying to catch the piece controlled by the Survivor player, but the pursuers are more restricted: the zombie pieces must always move, and must do so toward the survivor along a shortest path. Essentially, the zombies move in a 'brainless' way, which severely limits the design of algorithmic strategies. In a practical setting where the pursuers are robots or drones, the zombie strategies can be carried out by simpler/cheaper devices. This motivates the question: when can cops be replaced by zombies? In contrast to previous work that highlights graph classes where cops are significantly more useful when trying to catch the evader, we examine some situations where the simpler restricted movements imposed on zombies can be sufficient.

Fields of Study & Subjects

Advanced Graph Theory Research Optimization and Search Problems Complexity and Algorithms in Graphs

Publication details

Journal / source
DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)
Publication date
1 January 2026
Language
EN