Seeing is not believing in limited visibility cops and robbers
By: Bojan Bašić , Alfie Davies , Aleksa Džuklevski and more
Potential Business Impact:
Cops need fewer players to spot a robber.
We consider the model of limited visibility Cops and Robbers, where the cops can only see within their $l$-neighbourhood. We prove that the number of cops needed to see the robber can be arbitrarily smaller than the number needed to capture the robber, answering an open question from the literature. We then consider how close we can get to seeing the robber when we do not have enough cops, along with a probabilistic interpretation.
Similar Papers
Capturing an Invisible Robber using Separators
Discrete Mathematics
Find invisible robbers faster using a new map.
Cops and Robbers for Graphs on Surfaces with Crossings
Discrete Mathematics
Makes it easier to catch a robber in a game.
Reasoning under uncertainty in the game of Cops and Robbers
Logic in Computer Science
Tracks how players learn in guessing games.