The role of information in the cop-robber game

AbstractWe investigate the role of the information available to the players on the outcome of the cops and robbers game. This game takes place on a graph and players move along the edges in turns. The cops win the game if they can move onto the robber’s vertex. In the standard formulation, it is assumed that the players can “see” each other at all times. A graph G is called cop-win if a single cop can capture the robber on G. We study the effect of reducing the cop’s visibility. On the positive side, with a simple argument, we show that a cop with small or no visibility can capture the robber on any cop-win graph (even if the robber still has global visibility). On the negative side, we show that the reduction in cop’s visibility can result in an exponential increase in the capture time. Finally, we start the investigation of the variant where the visibility powers of the two players are symmetrical. We show that the cop can establish eye contact with the robber on any graph and present a sufficient condition for capture. In establishing this condition, we present a characterization of graphs on which a natural greedy pursuit strategy suffices for capturing the robber