Randomized pursuit-evasion with limited visibility

Abstract We study the following pursuit-evasion game: One ormore hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gatherinformation about the location of the hunters but it can see them only if they are located on adjacentnodes. We show that two hunters suffice for catching rabbits with limited visibility with high probability.We distinguish between reactive rabbits who move only when the hunter is visible and general rabbits whocan employ more sophisticated strategies. We present polynomial time algorithms that decide whether a graph G is hunter-win, that is, if a single hunter can capturea rabbit of either kind on G