Cops and Robbers
The original definition
Let G be a graph, n the number of cops, C the player for the cops
and R the player for the robber.
The game begins with C choosing n vertices of G as initial vertices
for the cops. Then, R chooses a starting vertex for the robber.
After that, both players move in alternating turns with C beginning.
A move consists of choosing new vertices for each of the agents under
a player's control. An agent can move to any neighboring vertex of
its current position or pass and remain in the same vertex.
The goal of C is to eventually move one of his cops onto the same
vertex as the robbers, thus capturing the robber. R's goal is to evade
capture as long as possible.
The game is played with perfect information,
i.e. both players know all agent positions at all times.
The number of steps the cops (C) have to take to capture the robber if both
players play optimally is called the search time of a graph.
This version was first independently studied by Nowakowski and Winkler (1983)
and Quillot (1978,1983). (see the publication
section).
Variations
There have been many variations studied in the literature.
(see publications)
graph sweeping/searching
The robber and the cops move along the edges. The robber with infinite
speed. The cops have to clear/sweep the graph. Think of the robber as
beeing some kind of gas that has spread along the graph and the cops
having to clean the graph.
imperfect information
Both, the robber and the cops can be supplied with only limited information.
However, usually only the cops get constrained whereas the robber is
left with full information about the game.
different speeds
The cops and the robber can have different speeds. Either having one
cop that is faster than the robber or multiple slower cops that try to
catch a faster robber.
directed vs. undirected graphs
Undirected (reflexive) graphs have been studied for quite a while.
Despite the many remaining open problems there is nearly nothing
known about directed graphs.
website last updated on 2008/11/17
contact