Randomized Pursuit-Evasion with Limited Visibility
Volkan Isler
Abstract We study the following pursuit-evasion game: One or more hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gather information about the location of the hunters but it can see them only if they are lo cated on adjacent no des. 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 who can 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 capture a rabbit of either kind on G. 1 Intro duction Pursuit-evasion games are problems of fundamental interest in many diverse fields such as computer-science, operations-research, game theory and control theory. The goal of a pursuit-evasion game is to find a strategy for a pursuer trying to catch an evader who, in turn, tries to avoid capture indefinitely. The game has many variations based on the environment in which it is played (E.g. plane, grid, graph), the information available to the the players (Do they know each others' positions all the time? Do es the pursuer know evader's strategy?), the controllability of their motion (Is there a bound on their speed? Can they turn whenever they want?), and the meaning of a capture (whether the evader must be intercepted, seen or surrounded). Earlier studies of pursuit-evasion were motivated by control tasks such as intercepting missiles [4]. The problem is addressed in the robotics community for its applications in collision avoidance, search and rescue, and
 Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA. Email: isleri@cis.upenn.edu. Supported in part by NSF-IIS-0083209, NSFIIS-0121293 and MURI DAAH-19-02-1-03-83  Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA. Email: kannan@cis.upenn.edu. Supported in part by NSF Grants CCR0105337 and CCR9820885.  Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA. Email: sanjeev@cis.upenn.edu. Supported in part by an Alfred P. Sloan Research Fellowship and an NSF Career Award CCR-0093117.

Sampath Kannan

Sanjeev Khanna

air-traffic control [10, 9]. In these models typically the motion of the evader is modeled by a stochastic process. However, recently there has been increasing interest in modeling games where the evader is more "intelligent" and has certain sensing capabilities [18]. Pursuitevasion games on graphs [17, 15, 13, 12, 6, 1] have been studied not only for their applications in network security and proto col design (e.g. [3, 11]) but also for their relations to fundamental properties of graphs such as vertex separation [7]. A remark about the terminology: In the literature, the names pursuer-evader, cop-robber, monster-princess, hunter-rabbit, sheriff-thief have been used somewhat synonymously. We adopt the hunterrabbit term for it emphasizes the discrete nature of the game [5, 1]. In this paper, we address a different aspect of the problem that has not received much attention so far. We study the relationship between the information available to the rabbit and the conditions to capture it. The basic model of our game is as follows: The players are located on the no des of a graph. At every time step, they move to nodes in their neighborhoods (which includes the current node) simultaneously. We say a rabbit is caught or captured if at the beginning of a time step it occupies the same node as a hunter. We asso ciate the information available to the rabbit with its visibility. If the rabbit has complete information about the location of the hunter(s) during the entire game, we say the rabbit has ful l visibility. On the contrary, if the rabbit has no information about the hunters, then we say it has no visibility. In our present work, we study the game when the rabbit has limited visibility. That is, it can only see the nodes that are adjacent to its current location. When the hunter is located at an adjacent node, the rabbit has complete information about his location. However, if the hunter is not visible, then the rabbit must infer the hunter's lo cation based on the time and location of their last encounter. Note that this model is different from the "visibility-based pursuit evasion" work [9, 16], where the goal is to eventually "see" an evader which has complete visibility and unbounded speed. Recently, Adler et al. studied this game when the rabbit has no visibility [1]. They showed that a single hunter can catch the rabbit on any (connected) graph.

Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

1060


The full visibility version has also been studied [15, 6]. It is known that under the full-visibility mo del, the class of graphs on which a single hunter suffices is the class of dismantlable graphs. The number of hunters necessary to capture the rabbit on a graph G is known as the cop (hunter) number of G. It is known that [2] the cop number of planar graphs is at most 3 but the cop number of general graphs is still an open question [14, 8]. We will fo cus on randomized strategies. The previous bo dy of work for the full visibility case [15, 6, 14, 8, 2] derandomized the game by forcing the players to move in turns, rabbit followed by the hunter. Note that when the players move simultaneously, the game is not well-defined for deterministic strategies: Suppose the game is played on a complete graph. In this case it is easy to see that a single hunter can catch the rabbit simply by guessing its lo cation in the next turn. However, if the hunter's strategy is deterministic, knowing it, the rabbit would never get caught. Similarly, the hunter could always catch the rabbit in a single move if he knew its strategy. Our results and techniques: Our main result is an algorithmic characterization for the limited visibility case. We show that two hunters always suffice on general graphs and present a polynomial time pro cedure that decides whether a single hunter is sufficient to capture the rabbit on an input graph G. In order to obtain an efficient decision pro cedure, we establish that the uncertainty in rabbit's knowledge of hunter's lo cation satisfies an interesting monotonicity property. This monotonicity property turns out to be crucial for obtaining a polynomial time characterization. In the winning strategy for two hunters, a central component is to have one hunter mainly fo cus on keeping the rabbit on the move. This motivated us to study a natural class of reactive rabbit strategies, where the rabbit moves only when the hunter is in its sight. We show that the class of hunter-win graphs (i.e graphs on which a single hunter suffices) against general rabbits is strictly smaller than the class of hunter-win graphs against reactive rabbits. We present a characterization algorithm for reactive rabbits as well. The characterization algorithms presented mark pairs of vertices according to certain rules, where the pairs correspond to players' positions. To understand the corresponding hunter strategies on hunterwin graphs, we first present a hunter strategy for the full visibility case. Next, we show that omitting one of the rules from the characterization algorithms yields an algorithm that recognizes graphs that are hunterwin against rabbits with full visibility. Using these two results, we show how the hunter exploits the limited visibility if the game is played on a graph G such that

on G, the hunter can win against a rabbit with limited visibility but not against a rabbit with full visibility. We note that when the rabbit's visibility is extended ~ to distance 2, there exist graphs for which ( n) hunters are necessary. Organization of the pap er: The paper is organized as follows: In Section 2, we review necessary concepts that will be used throughout the paper. In Section 3 we present a winning strategy for two hunters on general graphs. Next, we study the graphs on which a single hunter suffices, both for reactive (Section 4.1) and general rabbits (Section 4.2). Section 5 is dedicated to the study of hunter strategies on hunter-win graphs. A gap example distinguishing the power of the two types of rabbit strategies is also presented in Section 5. We conclude the paper with a discussion on extensions of our work. 2 Preliminaries Throughout the paper, we use the notation N (v ) to denote the set of vertices that are adjacent to v and we always assume that v  N (v ). Unless otherwise stated, n denotes the number of vertices. The game we study is formally defined as follows: It is played in rounds. In the beginning of a round, suppose a player (either a hunter or a rabbit) is lo cated at vertex v . First, the player checks N (v ) and if there is another player located at a vertex u  N (v ), this information is revealed to the player. In this case we say the two players see each other. Next, all the players make a decision about where to move and choose a vertex in their neighborho o ds. At the end of the round, all players move to their chosen vertex simultaneously. A hunter catches the rabbit if they are located on the same vertex. A reactive rabbit strategy is a rabbit strategy where the rabbit is not allowed to move from a vertex v unless the hunter is in N (v ). A rabbit strategy is general if it is not reactive. In other words, the rabbit can move even if the hunter is not visible. A (resp. non-)reactive rabbit is a rabbit that employs a (resp. non-)reactive strategy. A graph G is hunter-win against reactive rabbits if there exists a hunter strategy that catches any reactive rabbit on G with non-zero probability for all possible starting configurations. A graph that is hunterwin against general rabbits is defined similarly. Configuration versus state: For a single hunter game, a configuration refers to an ordered pair (h, r) which corresponds to the lo cations of the hunter and the rabbit respectively. Note that this information may not be available to the rabbit at all times due to its limited visibility. A configuration (h, r) is adjacent if h  N (r). We use the notation < H, r > to denote the state of the game where r is the lo cation of the

1061


rabbit and H corresponds to the set of vertices where the hunter can possibly be lo cated. For the full visibility case, if the current configuration is (h, r), the state is < {h}, r >. For the zero visibility case, the state is either < G - {r}, r > or < {r}, r >. For the limited visibility case that we study, state has a more complex structure, and it evolves over time even when neither the hunter nor the rabbit is in motion. Suppose u and v are two no des of a graph G such that N (u)  N (v ). Then, the operation of deleting u from G is called a folding of G and we say u folds onto v . A graph is called dismantlable if there is a sequence of folds reducing it to a single vertex. We say u eventual ly folds onto v , if there is a sequence u0 = u, u1 , . . . , uk = v such that ui folds onto ui+1 , 0  i < k . Let G be a dismantlable graph and  be a folding sequence reducing G to a single vertex v . We can visualize  as a tree T whose vertices are the vertices of G such that when ro oted at v every vertex in T is folded onto its immediate parent. If a graph G is not dismantlable, this means that after a sequence of foldings  it reduces to a graph H which can not be folded any further. We refer to the graph H as the residual graph of G, or just the residual, if G can be inferred from the context. It is known that the residual is unique up to isomorphism [6]. We can visualize the folding pro cess for non-dismantlable graphs as a forest of trees Th hanging from each vertex h  H (see Figure 2). Th is composed of vertices that eventually fold onto h and each vertex is folded onto its parent. We define  (u) = w if and only if u  Tw , w  H . We note that the tree representation depends on the folding sequence  and in general it is not unique. 3 A winning strategy with two hunters In this section, we present a strategy with two hunters that catches the rabbit on any graph. In general, a single hunter can not always capture the rabbit. This can be seen by considering a cycle of of length at least 4 as the input graph: The rabbit's strategy is to wait until the hunter becomes visible and move to its neighbor which do es not contain the hunter. This strategy guarantees that it will never get caught. The strategy of the two hunters is divided into epo chs that are comprised of two phases. An epoch starts with the hunters lo cated at a predetermined vertex. The first phase starts at time t = 1. In Phase One, two hunters move together and their goal is to see the rabbit. To achieve this, the hunters generate a random vertex label v  {1 . . . n} and move together to v . Afterwards, they wait at v until either (t mo d n) = 0 or the rabbit becomes visible. If the rabbit becomes visible at any time, the first phase is over

and the second phase starts. Otherwise, the hunters repeat the same process by generating a new label v . We claim that the first phase lasts only n2 log n steps with high probability. To see this, let r1 , r2 , . . . be the lo cation of the rabbit at times n, 2n, 3n, . . . Suppose the hunters have not seen the rabbit until time i × n. At that time, the probability that they generate a label in 1 N (ri+1 ) is at least n . Since they generate a label after every n steps, the first phase will be over in n2 log n steps with high probability. In Phase Two the hunters try to catch the rabbit as follows: Suppose the second phase starts at time t = t1 and let ti = t1 + (i - 1). At that time both hunters H1 and H2 are at vertex h and the rabbit is at vertex r, with r  N (h). For the rest of the second phase, let ri denote the position of the rabbit at time t = ti and let us define r0 = h. The strategy of H1 is as follows: At time t = ti , he 1 is lo cated at ri-1 . With probability p1 = n2 , he attacks the rabbit by generating a random neighbor of ri-1 and going there in the next step. With probability 1 - p1 , he chases the rabbit by going to ri in the next step. The second phase ends with failure if H1 attacks and misses the rabbit. The strategy of H2 is based on the following observation: If H1 chases the rabbit for more than n steps, the rabbit must revisit a vertex by the pigeonhole principle. Let u be the first vertex revisited and suppose at time tr , the rabbit visits a vertex v  N (u) for the first time before revisiting u. The goal of H2 is to enter v at the same time with the rabbit. To achieve this, first he guesses u, v and tr . In order to reach u, he chases H1 by moving to his lo cation in the previous time step until u. Afterwards, H2 waits until time t = tr - 1 and goes to v from u. We say H2 is in chasing mode if he is following H1 and he is in attacking mode after he arrives at u. The second phase ends with failure if H2 misses the rabbit when it arrives at v . To summarize, at time t = t1 , the hunters are at r0 and the rabbit is at r1 . When the hunters are chasing, the lo cations of the rabbit, H1 and H2 at time ti are ri , ri-1 , ri-2 respectively. The phase ends when either hunter attacks. If no hunter attacks within n2 steps, they end the phase and move to the predetermined vertex to start a new epo ch. Next, we state the crucial property of the strategy of the hunters. Lemma 3.1. During Phase Two, the rabbit can not distinguish between the modes of hunter H2 . Proof. If the attacking mo de starts at time t = t1 , the lo cation of H2 is the same for both mo des. If it starts afterwards, we show that if the rabbit sees H2 , it will get caught with non-zero probability.

1062


Suppose the rabbit sees H2 at time t = t2 which implies r2  N (r0 ). In this case, with probability at least p1 , H1 can decide to attack from r0 to r2 at time n t = t1 and catch the rabbit. Next, suppose the rabbit sees H2 at time t > t2 . If H2 was in chasing mo de at that time, the fact that rabbit sees H2 implies ri  N (ri-2 ). In this case as well, H1 could decide to attack in the previous step and catch the rabbit with probability p1 . Therefore H2 must be n invisible to the rabbit during the chasing mo de. But, H2 will also be invisible in the attacking mo de because as so on as the rabbit enters a vertex v where it can see H2 , H2 can catch it by guessing v and the arrival time correctly. Therefore in order to avoid getting caught, the rabbit must avoid seeing H2 . But then the information available to the rabbit will be same, no matter which mo de H2 is in: H2 is out of its sight since the beginning of the second phase.

to the class of hunter-win graphs against general rabbits. The answer turns out to be negative: The graph in h r

Figure 1: This graph is hunter-win against reactive rabbits but not against general rabbits.

Figure 1 is hunter-win against reactive rabbits. The input graph consists of a cycle and the gadget shown in the figure. It is easy to see that any rabbit can be driven into the gadget by simply chasing it along the cycle. It can also be verified that, once the rabbit is in the gadget, the hunter can reach a vertex whose neighborho o d dominates rabbit's neighborho o d without being seen. In this case the reactive rabbit would never leave the gadget and get caught. However, a general Lemma 3.2. During Phase Two, the hunters succeed rabbit can keep moving in the opposite direction of with non-zero probability. where it saw the hunter last until it leaves the gadget. If the cycle is big enough, the hunter can not reach Proof. As discussed previously, after the start of the the other entrance of the gadget before the rabbit and second phase, the rabbit must revisit a vertex u at time therefore a general rabbit is safe on this graph. k  n. If the rabbit do es not see H2 until t = k , H2 1 can catch it with probability n3 at least by guessing 4.1 Characterization of hunter-win graphs tr , u, v  n. Note that H1 will still be chasing the rabbit against reactive rabbits In this section, we describe k 1 with probability at least 1 - n2  1 - n . On the other an algorithm that recognizes hunter-win graphs against hand, if the rabbit sees H2 , it is caught with probability reactive rabbits. The algorithm marks configurations 1 1 at least n3 = min{ p1 , n3 }, by Lemma 3.1. (h, r) according to the following rules. n The length of an epo ch is O(n2 log n): Phase One lasts O(n2 log n) time with high probability and Phase Two lasts (n2 ) steps. We have established that in Phase Two, the rabbit is caught with probability at 1 least n3 . Therefore after n3 log n epo chs, each of which last O(n2 log n) steps at most, the rabbit will be caught, yielding our main result. Algorithm Mark-Reactive: Mark all configurations (v , v ) for every vertex v . (Initialization) Rep eat Mark (h, r) if for all r  N (r), there exists a vertex h  N (h) with (h , r ) marked. (Stride Rule) For all (h , r) that are marked, for all h  N (h ) \ N (r), mark (h, r). (Stealth Rule) Theorem 3.1. Two hunters can catch a rabbit with Until no further marking is possible. limited visibility on any graph with high probability. Next, we prove the soundness (if all configurations are marked, then the graph is hunter-win) and completeness (if the graph is hunter-win, then all configurations will be marked) properties of the marking algorithm. Soundness: The pro of is by induction on the round k in which a configuration is marked. When k = 1 only the configurations (v , v ) are marked and the hunter trivially wins the game in these configurations. Suppose the configurations marked in the first k rounds are sound and consider the configuration (h, r)

4 Hunter-win graphs In this section, we start the study of graphs on which a single hunter suffices. An interesting feature of the strategy of two hunters is that one hunter makes the rabbit move constantly, therefore forces it into making mistakes. This suggests that moving when a hunter is not visible may be a disadvantage for the rabbit. To study this phenomenon we intro duce reactive strategies where the rabbit moves only when the hunter is visible and ask the question whether the class of hunter-win graphs against reactive graphs is equivalent

1063


marked during step k + 1. If (h, r) was marked using the stride rule, during the execution of the game, the hunter can force a configuration marked during the k th step with non-zero probability. Hence these configurations are sound. If, on the other hand, the configuration (h, r) is marked by the stealth rule, we observe that the rabbit will remain at vertex r since the hunter is out of its sight and hence hunter can reach the configuration (h , r) which has been marked during the previous steps. Therefore the stealth rule is also sound by the inductive hypothesis. Completeness: Clearly, if the rabbit is captured the game ends at a marked configuration. Otherwise, we show that the rabbit can always stay in an unmarked configuration and hence never get caught. Suppose there is an unmarked configuration (h, r) and the hunter and the rabbit are at vertices h and r respectively. There are two cases: If h  N (r), the rabbit must have a move to a vertex r such that there exists no h  N (h) with (h , r ) is marked. Otherwise (h, r) would be marked by the stride rule. On the other hand, if h  N (r), no matter which vertex h the hunter moves, / (h , r) is unmarked. Otherwise (h, r) would be marked by the stealth rule. We can now state the result of this section which follows from the soundness and completeness of the marking algorithm.

configuration from any starting configuration (h, r). The proof of Proposition 4.1 is implicit in the strategy presented in Section 3. During Phase One, the twohunters act as one and we showed that their strategy ensures that the hunters and the rabbit will end up in adjacent vertices in n steps with non-zero probability. This means that, no matter which path rabbit takes, there exists a hunter-path of length at most n that leads to an adjacent configuration. Proposition 4.2. A graph G is hunter-win if and only if the hunter wins starting from any adjacent configuration. Proof. If the graph is hunter-win, the hunter must win from all starting configurations including the adjacent ones. Conversely, if the hunter can win from any adjacent configuration, then starting from any configuration he can reach an adjacent configuration by Proposition 4.1, and win the game from here on.

Therefore by Proposition 4.2, on a hunter-win graph, we can assume that the game starts from an initial configuration where the players see each other. In addition, without loss of generality, we assume that the rabbit moves so as to maximize the time taken for capture and the hunter moves so as to minimize it. We can view any hunter-win game as a sequence Theorem 4.1. A graph G is hunter-win against reac- of rounds R1 , . . . , Rp where each round starts with the tive rabbits if and only if the algorithm Mark-Reactive players located at adjacent vertices. Hence, the rabbit has full knowledge of the hunter's position. Clearly, marks al l configurations. there are at most n2 rounds and the rounds do not 4.2 Characterization of hunter-win graphs repeat. against general rabbits For reactive rabbits, it is 2 easy to see that on a hunter-win graph every rabbit Lemma 4.1. The length of each round is bounded by n . walk can be intercepted (i.e. the rabbit gets caught) by the hunter in O(n3 ) steps. However, it is far from being clear that such a polynomial length intercepting Proof. Partition the round into segments of length n walk (i.e a witness) exists for non-reactive rabbits. The each. The rabbit must revisit a vertex r within the difficulty is that at any point in time, the rabbit can same segment. Let < H1 , r1 > and < H2 , r2 > be infer a subset H  V of possible hunter lo cations and the state of the game during the first and second visits. plan its motion accordingly. This suggests that the state First, we show that H1  H2 . This is because, between of the game may require specifying arbitrary subsets of r1 and r2 , the rabbit can not visit any vertex u with vertices, potentially leading to exponential witnesses. u  N (h), h  H1 : If the hunter is at h, the rabbit Fortunately, we can establish a monotonicity property would be captured. Next, if H1 = H2 , then the part of the hunter strategy between r1 and r2 is redundant and to establish once again polynomial-size witnesses. hence the hunter can shorten the game. Therefore as the Let < H, r > be the state of the game where H is the set of possible hunter lo cations when the rabbit is rabbit keeps visiting the same vertex, its uncertainty is at r. When the rabbit and the hunter are at adjacent monotonically increasing and after at most n revisits vertices r and h respectively, the rabbit knows the the state of the game becomes < G - N (r), r >. In hunter's position with certainty and therefore H = {h}. this case, either the rabbit gets caught if it moves or the hunter reveals himself, ending the round. Since the Now suppose the game starts at configuration (h, r). rabbit has to revisit a vertex every n steps and there Proposition 4.1. The hunter can reach an adjacent are at most n revisits, the lemma follows.

1064


Since the length of a round is bounded by n2 and there are n2 rounds, we conclude that the total length of a hunter-win game is O(n4 ). Our characterization algorithm for general rabbits is based on the existence of such a polynomial size witness. We wil l mark only adjacent configurations: if the adjacent configurations are all marked, by Proposition 4.2 the hunter wins from all starting configurations. A general rabbit can move even if the hunter is not visible. In order to capture this capability we need to generalize the stealth moves, described next. 4.2.1 Stealth Moves A k -stealth move from configuration (h, r) with h  N (r) to a marked configuration (h , r ) is defined as follows: For every rabbit path Pr = {r, r1 , . . . , rk = r } of length k , the hunter has a / path Ph = {h, h1 , . . . , hk = h } such that hi  N (ri ) for i = 1, . . . , k - 1, hk  N (rk ) and (hk , rk ) is marked. We refer to Ph as the stealth path corresponding to Pr . A configuration (h, r) is marked by the Stealth Rule if for all r  N k (r), there exists a k -stealth move to a marked configuration (h , r ). Note that the Stealth Rule for k = 1 subsumes the Stride Rule. Lemma 4.2. The markings corresponding to stealth moves are sound. Proof. Suppose all previously marked adjacent configurations are sound and consider the next adjacent configuration (h, r) marked by a stealth move of length k . At time t = 0 the rabbit is lo cated at r. Since we mark only the adjacent configurations, the state of the game is < {h}, r >. Take any rabbit path of length k , and suppose at time t = i the rabbit is at vertex ri . Let r1 , . . . , rp be the vertices accessible from ri in the remaining k - i steps and P1 , . . . Pp be the corresponding stealth paths such that at the end of k steps, Pi ends at vertex hi and (hi , ri ) is marked. Let Ei be the event that the hunter has chosen path Pi , i = 1, . . . , p and let hi be the ith vertex on Pi . The claim follows from the observation that no matter which path Pi the hunter cho oses, the information available to the rabbit is the same, namely hunter was not visible for the last i steps. Therefore the state of the game is < H, r > where {hi |1  i  p}  H . Since the rabbit can not distinguish between the events Ei , no matter which final destination rj it cho oses, the hunter can be at the corresponding vertex hj and arrive at the already marked configuration (hj , rj ). The stealth moves starting from configuration (h, r) and ending at configuration (h , r ) can be computed efficiently by dynamic programming. We will need an intermediate lo ok-up table T , with T [h, r, h , r , k ] = TRUE if and only if for any rabbit

path {r, r1 , . . . , rk = r } of length k there is a stealth path of length k that starts from h and ends at h . The entries of the Table T are filled as follows: (i) T [h, r, h , r , 0] = TRUE iff h = h , r = r and  h N (r ). (ii) T [h, r, h , r , 1] = TRUE iff h  N (h), r  N (r) and h  N (r ). (iii) T [h, r, h , r , k + 1] = TRUE iff for all u  N (r) there is a vertex v  N (h) \ N (u) with T [u, v , h , r , k ] = TRUE, for 1  k  n2 . We now present a marking algorithm that uses the look-up table T to compute the stealth moves. Algorithm Mark-General: Mark all configurations (v , v ) for every vertex v . (Initialization) Rep eat For all configurations (h, r) with h  N (r), mark (h, r) if there exists an index k  n2 such that r  N k (r), there exists a vertex h with T [h, r, h , r , k ] = TRUE and (h , r ) is marked. (Stealth Rule). Until no further marking is possible. Lemma 4.3. If the graph is hunter-win, then the marking algorithm Mark-General wil l mark al l adjacent configurations. Proof. Let (h, r) be an adjacent configuration left unmarked after the execution of algorithm Mark-General. We claim that the rabbit can get to an adjacent configuration (h , r ) that is unmarked. Suppose not. This means that for any rabbit path r, r1 , r2 , . . . , rk there is a hunter path h, h1 , h2 , . . . , hk with hk  N (rk ) and (hk , rk ) is marked. By Lemma 4.1, we have k  n2 . This implies that (h, r) would be marked by the stealth rule, which gives us the desired contradiction. Therefore, starting from any unmarked adjacent configuration (h, r), the rabbit can reach another unmarked adjacent configuration. This means that the rabbit will never get caught, since a capture implies that the game enters the configuration (v , v ) for some vertex v which is a marked adjacent configuration. Theorem 4.2. A graph G is hunter-win against general rabbits if and only if the algorithm Mark-General marks al l adjacent configurations. Proof. If all the configurations are marked, G is hunterwin due to the fact that the stealth rule is sound (Lemma 4.2). Conversely, if there is an unmarked configuration, the rabbit is never caught by Lemma 4.3.

1065


5 Complete visibility and dismantlable graphs When the rabbit has full visibility, the stealth rule do es not make sense. In fact, we will show that the stride rule against reactive rabbits is sound and complete against rabbits with full visibility. Algorithm Mark-FullVisibility: Mark all configurations (v , v ) for every vertex v . Rep eat Mark (h, r) if for all r  N (r), there exists a vertex  h N (h) with (h , r ) marked. (Stride Rule) Until no further marking is possible. It turns out that the algorithm Mark-FullVisibility recognizes hunter-win graphs against rabbits with full visibility. H v w
T

x

u

u
w

Figure 2: Visualization of the folding pro cedure for a non-dismantlable graph. The vertices w,v and x are in the residual H . Since there is no edge from w to x, the edges shown with dashed lines can not exist. We will need the following property of nondismantlable graphs: Proposition 5.1. Let G be a non-dismantlable graph,  be a folding sequence and H be the residual. Let x and w be two distinct vertices in H and Tx and Tw be the corresponding folding trees (see Figure 2). If there exist a vertex u  Tw that is adjacent to a vertex u  Tx , then x  N (w).

Proof. Without loss of generality, suppose u was folded before u . This implies that the parent of u must be adjacent to u . We replace u with its parent and continue this pro cess of propagating the edge between As stated earlier, it has been shown that the class u and u , which must eventually reach the ro ots w and of graphs that are hunter-win against rabbits with full x of the corresponding trees. visibility are precisely the class of dismantlable graphs [6]. Therefore we obtain: Theorem 5.1. The algorithm Mark-Ful lVisibility marks al l configurations if and only if the input graph Corollary 5.1. A graph G is hunter-win against rabis dismantlable. bits with ful l visibility if and only if the algorithm Mark-

Proof. Suppose the input graph G is dismantlable. We can prove that all configurations will be marked by induction on the order of G. Since G is dismantlable, it must have two vertices u and v with N (u)  N (v ). Let G = G - {u} and run algorithm Mark-FullVisibility on G . Suppose, inductively, that all configurations in G are marked. Consider the marking algorithm for G which marks (u, u) first and simulates the marking algorithm on G afterwards. In addition, whenever (x, v ) is marked for a vertex x  G , we also mark (x, u). This is possible since (x, v ) is marked implies that for all v  N (v ), there exists a vertex x  N (x) with (x , v ) marked and N (u)  N (v ). Next, we show that all the configurations (x, y ) in G will also get marked in G. Suppose there exists a configuration (x, y ) that is marked in G but not in G. Consider the first such configuration that is discovered in the marking of G. It must be that u  N (y ) and that for all x  x, (x , u) is not marked at this point. Also, v  N (y ) since N (u)  N (v ). Now using the fact that (x, y ) gets marked at this stage in G , we know that there exists  , N (x) such that (x v ) is already marked. But x , then (x u) must also be marked at this point according to the mo dified marking rule. A contradiction! Thus, any (x, y ) marked in G will also be marked in G. It follows that for any x such that (x, v ) is marked in G , we can mark (x, u) in G. It is easy to see that for any x, the configuration (u, x) will also be marked in G since u is adjacent to v and, by the argument above, for all x  N (x), (v , x ) is marked. Now suppose the input graph is not dismantlable. Let  be a sequence of folds reducing G to a residual graph H . For any two vertices u  G and v  H , we claim that (u, v ) is unmarked if  (u) = v . Suppose this is not true and let (u, v ) be the first marked configuration such that  (u) = v (Figure 2). Let w =  (u), w = v . Note that v must have a neighbor x such that x  N (w), otherwise v would fold onto / w. When (u, v ) gets marked, there must be a vertex u  N (u) such that (u , x) is marked. If  (u ) = x, this would imply x  N (w) by Proposition 5.1. So it must be the case that  (u ) = x. But then, the fact that (u , x) is marked contradicts with the fact that (u, v ) is the first configuration marked with  (u) = v . Therefore, we conclude that if the graph is not dismantlable, the marking pro cess will not mark all configurations.

1066


FullVisibility marks al l configurations.

3

5

4

6

12

11

h  N (r) and the rabbit takes the path r  r  r uch that the hunter is not visible from r . It can be shown, by enumeration, that for any such vertices h, r, r and r , the hunter has a path h  h  r that captures the rabbit. Therefore the rabbit can not have a non-reactive strategy either and the graph is hunter-win against both types of rabbits. We conclude this section with an interpretation of Theorem 5.1: If G is a graph that is hunter-win against rabbits with limited visibility but not against rabbits with full-visibility, the hunter captures the rabbit with limited visibility using the stealth moves. 5.1 Hunter strategy for dismantlable graphs Given a folding tree T rooted at vertex v , consider the vertex r rabbit is located. We say the hunter is an ancestor of the rabbit if he is lo cated on the path from r to v . Suppose the vertices of T are ordered by their deletion times. The hunter strategy is based on the following two lemmas.
r

s

9

10

2

8

1

7

Figure 3: This graph is hunter-win against rabbits with limited visibility. However, a rabbit with full visibility never gets caught. We know that there are non-dismantlable graphs that are hunter-win against rabbits with limited visibility. An example is shown in Figure 3. The labels on the vertices indicate their folding order: First, vertex 1 folds onto vertex 2, afterwards vertex 2 folds onto vertex 9, etc. After folding vertices 1 to 8, vertices 9 to 12 can not be folded, leaving a four-cycle as the residual. Therefore this graph is not dismantlable and consequently it is not hunter-win against rabbits with full visibility. To see that the hunter wins against rabbits with limited visibility, let us define the mapping p : V  V where V is the set of vertices. For v  V with 1  v  8, p(v ) is the vertex which v folds onto. We define p(9) = 2, p(10) = 8, p(11) = 6 and p(12) = 4. The first observation is that the hunter wins the game if he can force the rabbit to go to vertex 1 while he is at vertex 2. Next, we observe that if the rabbit is at vertex v = 1 and the hunter is at p(v ), the rabbit must move to a lower numbered vertex. Now suppose the rabbit is reactive. In this case, it can be verified that for any rabbit location r and for any hunter lo cation h  N (r), the hunter has / a path to p(r) that does not enter N (r). Therefore, by visiting p(r) repeatedly the hunter can force a reactive rabbit to eventually move to vertex 1 and win the game afterwards. Hence, the rabbit must have a non-reactive strategy, meaning that it must move when the hunter is not visible. Consider the first time this happens: Suppose the hunter and the rabbit are at vertices h and r with

h
h

h r
h

h r
r

r >r
>

r r r
>

h

h

r

<

r

r h

Figure 4: Hunter can always stay above the rabbit. The height of a vertex is proportional to its label. Lemma 5.1. Hunter can always maintain ancestry. Proof. Suppose the hunter is at vertex h and is an ancestor of the rabbit who is located at vertex r. Let r be the rabbit's lo cation in the next round. If h is a common ancestor of r and r on the folding tree T , then the lemma is trivially true. Otherwise, since h is an ancestor of r and (r, r ) is an edge, using basic properties of foldings it can be shown that h is adjacent to a vertex on the path that connects r to the ro ot of T . We show that there is always such a vertex h with h  r by a case analysis on r (See Figure 4). Suppose for contradiction h < r . We will show that h must be adjacent to r thus allowing the hunter to catch the rabbit in one step. Case (h > r > r): In this case all the ancestors of d h eleted before h (including r ) must have edges to h. Case (r > h): All the ancestors of r deleted before ( r including h) must have an edge to r . Case (r < r): All the ancestors of h deleted before r (including r ) must have an edge to h.

1067


In fact, not only the hunter can maintain ancestry, hunter is at h. We say hunter is an ancestor of the but also he can reduce his height in the tree gradually rabbit if there is a folding of the vertices such that in the corresponding forest representation, h is lo cated on and therefore get closer and closer to the rabbit. the path from r to the ro ot of the tree that contains r. Once the hunter establishes ancestry, it is easy to see that Lemma 5.1 and Lemma 5.2 still hold ­both for reactive and general rabbits. Therefore the hunter can win the game afterwards. Note that the hunter can trivially establish ancestry on dismantlable graphs. In addition, if we define each vertex as its trivial h C parent, it is clear that the rabbit wins the game if the Cp hp hunter can never become an ancestor. Therefore the class of hunter-win graphs is precisely the class of graphs r p(v ) on which the hunter can become an ancestor. One can Cr view the stealth moves as giving the hunter the power v to become an ancestor on non-dismantlable but hunterwin graphs such as the one in Figure 3. 6 Concluding Remarks Let us define rabbits with i-visibility as the rabbits who can see all vertices within distance i. It is known that one hunter always suffices to catch rabbits with 0-visibility [1]. In this paper, we studied rabbits with 1-visibility and established that 2 hunters always suffice to catch such rabbits. A natural question is how many hunters suffice when the rabbit has i-visibility. Surprisingly, the number of hunters required for 2visibility is unbounded: using the probabilistic metho d, one can sow that there exist random bipartite graphs h ~ where ( n) hunters are needed. Another aspect of the game is the time required to catch the rabbit. For 0-visibility, one hunter succeeds in time O(n log n) [1]. For 1-visibility we showed that ~ two hunters succeed in O (n5 ) time. However, it is not clear whether a single hunter can catch a rabbit on a hunter-win graph in polynomial time. We leave this as a direction for future work. References
[1] M. Adler, H. Racke, N. Sivadasan, C. Sohler, and ¨ B. Vocking. Randomized pursuit-evasion in graphs. ¨ Proceedings of the International Col loquium on Automata, Languages and Programming (ICALP), 2002. [2] M. Aigner and M. Fromme. A game of cops and robb ers. Discrete Applied Math, 8:1­12, 1984. [3] T. Basar and P. R. Kumar. On worst case design strategies. Computers and Mathematics with Applications: Special Issue on Pursuit-Evasion Differential Games, 13(1-3):239­245, 1987. [4] T. Basar and G. J. Olsder. Dynamic Noncooperative Game Theory. SIAM, 1998. [5] P. Bernhard, A.-L. Colomb, and G. P. Papavassilop oulos. Rabbit and hunter game: two discrete stochastic

Figure 5: Hunter can make progress every time the rabbit revisits a vertex. Lemma 5.2. Every time the rabbit revisits a vertex, the hunter can reduce its height in the tree while maintaining ancestry . Proof. Fix any rabbit cycle Cr and let v be the vertex with the lowest label on this cycle and p(v ) be its parent (see Figure 5). Since v was deleted first, p(v ) must have edges to the neighbors of v on the cycle, so we can make a new cycle by replacing v with p(v ). We continue this pro cess until the cycle reaches h, the lo cation of the hunter (this must happen since hunter is an ancestor at all times). Let us call this cycle C . Let Cp be the cycle just before C which contains h's child hp , instead of h. Consider the path P = {h}  (C  Cp )  {hp }. If the rabbit follows the cycle Cr , hunter can follow the path P and end up at hp which is lower than h. We are now ready to present the hunter strategy on a dismantlable graph G. First, the hunter builds the folding tree T for any folding sequence  . Afterwards, he simply guesses the vertex the rabbit will jump to and jumps to the lowest possible ancestor of this vertex (see Figure 5). By Lemma 5.1 he can always remain an ancestor of the rabbit. Further, he can reduce his height in T every time the rabbit revisits a vertex (Lemma 5.2). Since the tree has a finite height, he can eventually catch the rabbit. 5.2 Extension to non-dismantlable graphs For non-dismantlable graphs, we can extend the notion of ancestry as follows. Suppose the rabbit is at r and the

1068


[6]

[7]

[8]

[9]

[10]

[11]

[12] [13]

[14]

[15] [16]

[17]

[18]

formulations. Comput. Math. Appl., 13(1-3):205­225, 1987. G. Brightwell and P. Winkler. Gibbs measures and dismantlable graphs. J. Comb. Theory (Series B), 78, 2000. J. A. Ellis, I. H. Sudb orough, and J. S. Turner. The vertex separation and search numb er of a graph. Information and Computation, 113(1):50­79, 1994. S. Fitzpatrick and R. Nowakowski. Copnumber of graphs with strong isometric dimension two. ARS COMBINATORIA, 59:65­73, 2001. L. J. Guibas, J.-C. Latombe, S. M. LaValle, D. Lin, and R. Motwani. A visibility-based pursuit-evasion problem. International Journal of Computational Geometry and Applications, 9(4/5):471­, 1999. J. P. Hespanha, G. J. Pappas, and M. Prandini. Greedy control for hybrid pursuit-evasion games. In Proceedings of the European Control Conference, pages 2621­2626, Porto, Portugal, Septemb er 2001. I.Chatzigiannakis, S.Nikoletseas, and P.Spirakis. An efficient communication strategy for ad-hoc mobile networks. In Proc. of 15th Symposium on Distributed Computing (DISC'2001), pages 285­299, 2001. A. S. LaPaugh. Recontamination does not help to search a graph. J. ACM, 40:224­245, 1993. N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou. The complexity of searching a graph. J. ACM, 1988. S. Neufeld and R. Nowakowski. A game of cops and robb ers played on products of graphs. DISCRETE MATHEMATICS, 186:253­268, 1998. R. Nowakawski and P. Winkler. Vertex-to-vertex pursuit in a graph. Discrete Math, 43:235­239, 1983. S.-M. Park, J.-H. Lee, and K.-Y. Chwa. Visibilitybased pursuit-evasion in a polygonal region by a searcher. Proceedings of the International Col loquium on Automata, Languages and Programming (ICALP), 2076, 2001. T. D. Parsons. Pursuit evasion in a graph. In Y. Alavi and D. R. Lick, editors, Theory and Application of Graphs, pages 426­441. Springer Verlag, 1976. R. Vidal, O. Shakernia, J. Kim, D. Shim, and S. Sastry. Probabilistic pursuit-evasion games: Theory, implementation and exp erimental evaluation. IEEE Transactions on Robotics and Automation, 18:662­669, 2002.

1069