Combinatorics, Probability and Computing



Randomized Pursuit-Evasion in Graphs


MICAH ADLER a1, HARALD RÄCKE a2 1 , NAVEEN SIVADASAN a4 2 , CHRISTIAN SOHLER a3 and BERTHOLD VÖCKING a5 3
a1 Department of Computer Science, University of Massachusetts, Amherst, MA 01003-4610, USA (e-mail: [email protected])
a2 Heinz Nixdorf Institute and Faculty of Computer Science, Electrical Engineering and Mathematics, University of Paderborn, Germany (e-mail: [email protected])
a3 Heinz Nixdorf Institute and Faculty of Computer Science, Electrical Engineering and Mathematics, University of Paderborn, Germany (e-mail: [email protected])
a4 Max-Planck-Institut für Informatik, 66123 Saarbrücken, Germany
a5 Department of Computer Science, Universität Dortmund, 44221 Dortmund, Germany (e-mail: [email protected])

Abstract

We analyse a randomized pursuit-evasion game played by two players on a graph, a hunter and a rabbit. Let $G$ be any connected, undirected graph with $n$ nodes. The game is played in rounds and in each round both the hunter and the rabbit are located at a node of the graph. Between rounds both the hunter and the rabbit can stay at the current node or move to another node. The hunter is assumed to be restricted to the graph $G$: in every round, the hunter can move using at most one edge. For the rabbit we investigate two models: in one model the rabbit is restricted to the same graph as the hunter, and in the other model the rabbit is unrestricted, i.e., it can jump to an arbitrary node in every round.

We say that the rabbit is caught as soon as hunter and rabbit are located at the same node in a round. The goal of the hunter is to catch the rabbit in as few rounds as possible, whereas the rabbit aims to maximize the number of rounds until it is caught. Given a randomized hunter strategy for $G$, the escape length for that strategy is the worst case expected number of rounds it takes the hunter to catch the rabbit, where the worst case is with regard to all (possibly randomized) rabbit strategies. Our main result is a hunter strategy for general graphs with an escape length of only $\O(n \log (\diam(G)))$ against restricted as well as unrestricted rabbits. This bound is close to optimal since $\Omega(n)$ is a trivial lower bound on the escape length in both models. Furthermore, we prove that our upper bound is optimal up to constant factors against unrestricted rabbits.

(Received May 2 2002)
(Revised October 22 2002)



Footnotes

1 Partially supported by the IST Programme of the EU under contract number IST-1999-14186 (ALCOM-FT), DFG grant Me 872/8-1 and DFG Sonderforschungsbereich 376 ‘Massive Parallelität: Algorithmen, Entwurfsmethoden, Anwendungen’.

2 Partially supported by the IST Programme of the EU under contract number IST-1999-14186 (ALCOM-FT).

3 A preliminary version of this paper appeared in proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP), 2002.