Cop–robber guarding game with cycle robber-region

A cop–robber guarding game is played by the robber-player and the cop-player on a graph G with a partition R and 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 admits 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. In this paper, we show that the problem remains NP-complete even if R induces a 3-star and that the problem is polynomially solvable if R induces a cycle.