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

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.