Capture time in variants of cops & robbers games
Natasha Komarov · 2013
We examine variations of cops and robbers games on graphs. Our goals are to introduce some randomness into their study, and to estimate (expected) capture time. We show that a cop chasing a random walker can capture him in expected time n + o(n). We also discuss games in which the players move in the dark (showing that a cop can capture an immobile hider in time n on any graph and any robber in time n on Kn) and in which the players suffer various restrictions on their movements. Finally, we consider open problems, including the idea of a patrolling scheme—that is, a plan for the “beat” a cop ought to walk on a graph in order to maximize the danger for the robber of committing a crime at any given location.