Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2009-002 (January 13, 2009)

Cop-Robber Guarding Game with Cycle Robber Region
by Hiroshi Nagamochi

pdf File

A cop-robber guarding game is played by the robber-player and the cop-player on a graph $G$ with a bipartition $\{R,C\}$ of the vertex set. The robber-player starts the game by placing a robber (her pawn) on a vertex in $R$, followed by the cop-player who place a set of cops (her pawns) on some vertices in $C$. They take turns in moving their pawns to adjacent vertices. The cop-player moves the cops within $C$ to prevent the robber-player from moving the robber to any vertex in $C$. The robber-player wins if it gets a turn to move the robber onto a vertex in $C$ on which no cops situate, and the cop-player wins otherwise. The problem is to find the minimum number of cops that admit a winning strategy to the cop-player. It has been shown that the problem is polynomially solvable if $R$ induces a path, whereas it is NP-complete if $R$ induces a tree. It was open whether it is solvable or not when $R$ induces a cycle. This paper answers the question affirmatively.