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 places a set of cops (her pawns) on some vertices in C. The two players take turns in moving their pawns to adjacent vertices in G. 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 cop situates, 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.
展开▼
