Cops and Lethal Robber on Rings: A Distributed Perspective Amanpreet Singh Sainia , Ashish Saxenaa , Kaushik Mondala
arXiv:2609.06388v1 [cs.DC] 6 Sep 2026
a
Department of Mathematics, Indian Institute of Technology Ropar, Rupnagar, 140001, Punjab, India
Abstract The Cops and Robber game is extensively studied in the sequential setting where the main goal is to capture the robber. Capturing the robber means at least one cop, and the robber will be at the same vertex together at some time. There are several variants, including variants where the goal of the cops is to surround the robber. Surrounding the robber means there is at least one cop in each of the neighboring vertices of the robber’s position. In this paper, we introduce it in the distributed setting while empowering the robber by saying it can even kill cops. Specifically, in our model, the robber moves in odd rounds and has unbounded speed, cops move in even rounds, and if one or more cops move into a vertex where the robber is currently residing, all these cops get killed. We call this lethal robber. This also connects our work to the Intruder Capture and Black Hole Search problems by introducing an entity which is dynamic as well as lethal, a setting that, to the best of our knowledge, has not been studied. In this work, we introduce the lethal robber, define the cops and lethal robber problem in the distributed setting and study it on a static ring of size n. We prove n cops are not enough, even if all start from the same vertex, and provide an algorithm starting from an arbitrary initial configuration that requires n + ⌊log n⌋ + 4 cops in the worst case. Keywords: Cops, Lethal robber, Anonymous ring, Distributed algorithm, Deterministic algorithm. 1. Introduction The Cops and Robber is a pursuit-evasion game played in rounds on a finite graph G between a set of k ≥ 1 cops and a single robber. In its classical form, before starting the game, an initial position on the vertices of G is chosen first by the cops, then by the robber. Then, in each round, first the cops, then the robber, move to neighbouring vertices or (if allowed by the variant of the game) stay in the current location. The game ends if the cops capture the robber. That is, the robber and at least one cop occupy the same vertex, in which case the cops have won. The robber wins by forever avoiding capture; note that, in this case, the game never ends. Recently, Jungeblut et al. [17] introduced a variant that replaces capture with a stronger requirement: the cops must surround the robber, i.e., occupy all neighbours of the robber’s current position, thereby preventing any escape. This surrounding variant captures situations where containment, rather than direct capture, is the objective.
Most existing work assumes that interaction with the robber is safe, meaning that a cop can freely move onto the robber’s vertex without consequences. In this work, we depart from this assumption and consider a setting where the robber behaves as a lethal entity: any cop that moves onto the robber’s position is immediately destroyed without leaving any trace. At the same time, we restrict the robber’s power by disallowing it from moving onto vertices occupied by cops. Indeed, if such moves were permitted, the robber could eliminate all cops, making any meaningful notion of containment or surrounding impossible. This restriction ensures a well-defined and non-trivial objective, where the cops must coordinate to safely surround the robber. We call this problem the Cops and Lethal Robber game (CLR). A related variant has been studied in [6], where the robber is allowed to move onto a vertex occupied by cops and eliminate one of them; in particular, if two cops are present, the robber may eliminate one while the other can still capture it. In contrast, we adopt a stricter and more adversarial model: if multiple cops move onto the robber’s vertex simultaneously, all of them are destroyed. At the same time, CLR is closely related to the Intruder Capture (IC) problem [3], where the objective is to capture an intruder that may move arbitrarily fast and is aware of the positions of all agents. The challenge is to design a strategy that guarantees the intruder’s capture despite these advantages. Similarly, in CLR, the robber is arbitrarily fast, and the cops must progressively restrict its mobility until it is eventually surrounded. As in IC, the robber’s location is initially unknown. However, unlike IC, the robber in CLR is lethal, introducing a fundamentally new challenge, as any cop that encounters the robber is eliminated. A further connection can be drawn with the Black Hole Search (BHS) problem [12]. In BHS, a black hole is a lethal vertex that destroys any mobile entity entering it, and the objective is to identify its location. The lethal robber in CLR can be viewed as a dynamic counterpart of a black hole: any cop entering the robber’s vertex is destroyed. However, in contrast to BHS, where the lethal object is static, the robber is mobile, strategic, and actively attempts to avoid containment. Rather than only detecting the dangerous entity, a more meaningful objective is to capture or block its movement. Thus, CLR combines aspects of pursuit-evasion and lethal-environment, introducing challenges that are absent in either setting alone. In this work, we study CLR in the distributed setting. The details of the distributed model and problem definition are presented in the next section. 1.1. Model and the problem definition Network model: The network is modeled as an undirected, anonymous, port-labeled simple graph, denoted by G = (V, E), where V and E are the sets of vertices and edges, respectively. In this work, we consider G as a ring Cn , where n = |V |. The vertices are anonymous, and at each vertex v ∈ V , the incident edges are assigned distinct port numbers from the set {0, 1}. Port labels are local: an edge (u, v) ∈ E may have different port numbers at its two endpoints. Such labeling is necessary, as without port numbers it is impossible to distinguish among outgoing edges at a vertex [11]. 2
Cop model: We consider k ≥ 1 cops placed arbitrarily on the vertices of the ring Cn by an adversary. Each cop is assigned a unique identifier from the range [1, nλ ], where λ is a positive constant. The identifier of a cop c is denoted by c.ID. Each cop knows only its own identifier and has no information about the identifiers of other cops. Furthermore, the cops have no prior knowledge of the size or structure of the ring, the initial positions of other cops, or the distances between them. Each cop can distinguish between port 0 and port 1 at the node it resides at any round. Also, each cop is equipped with some memory. The system operates in synchronous rounds, starting from round 0. Following the classical setting, we assume that the cops act in even-numbered rounds. In each such round, a cop at a vertex v can observe the degree of v and the port numbers of all incident edges. During each even round, every cop executes a Communicate–Compute–Move cycle, in which it first communicates with all other cops present at the same vertex, then performs local computation to decide whether to move and, if so, selects a port number, and finally moves through the selected port, if any. Upon entering a vertex, each cop c records the port through which it arrived, denoted c.portin. Two cops crossing the same edge simultaneously in opposite directions cannot detect or communicate with each other. We say a configuration is rooted if all cops are initially co-located at one vertex, and scattered otherwise. Lethal robber model: We consider a lethal robber. Initially, the robber has complete knowledge of Cn , including the positions of all cops and their algorithms. This knowledge is available to the robber in every odd-numbered round. At a round, if the robber is at vertex u, it may either stay at u or move to a vertex v provided there exists a path from u to v with no vertex on that path occupied by any cop. The robber is also not allowed to move onto a vertex occupied by a cop. The robber has unbounded speed and thus can traverse any such path within a single round, but must move along the edges of the graph. The cops, on the other hand, do not know the location of the robber and can move only to an adjacent vertex in one round. If one or more cops move onto the vertex currently occupied by the robber, all such cops are destroyed without leaving any trace. Problem definition: The CLR game is played in rounds on the ring Cn between a set of k ≥ 1 cops and a single lethal robber. Before the start of the game, the cops are placed on the vertices of Cn by an adversary, after which the robber chooses its initial position on some vacant vertex. The cops have no knowledge of the robber’s location or the locations of the other cops. The game proceeds in synchronous rounds. The cops act in each even round, followed by the robber that acts in each odd round, according to the rules of the model. The cops win if they surround the robber; that is, at some round r, the robber is located at a vertex v ∈ V and all neighbors of v are occupied by cops. In this case, the robber cannot move and is captured. The robber wins by either eliminating all cops or forever avoiding being surrounded; that is, if the robber is at a vertex v, then at least one neighbor of v is not occupied by any cop. In the latter case, the game never ends. The objective is to design a distributed strategy for the cops that guarantees winning the game from any arbitrary initial configuration.
3
1.2. Related work The study of pursuit–evasion games on graphs is centered around the classical Cops and Robber model, introduced independently by Nowakowski and Winkler and by Quilliot [22, 23]. The extension to multiple cops and the notion of the cop number c(G) were formalized by Aigner and Fromme [1], who established foundational results such as the fact that three cops suffice for planar graphs. Since then, the classical model has been extensively studied; we refer to [5, 21] for comprehensive overviews. A√central open problem in this area is Meyniel’s conjecture, which asserts that c(G) = O( n) for any connected graph on n vertices [18, 2]. From a computational perspective, deciding whether c(G) ≤ k is NP complete [15]. Several variants of the classical Cops and Robber game have been proposed to study the effect of restricting the robber’s movement. In the restrictive vertex model of Burgess et al. [8], the robber is forbidden from entering vertices occupied by cops, a framework later extended by Bradshaw et al. [7]. This idea was generalized in the containment variant of Crytser et al. [9], where cops occupy edges and block the robber’s traversal. Related restrictive models have also been studied in other settings, such as the face-based variant for planar graphs introduced by Jungeblut et al. [16]; see also [24]. While these works focus on limiting the robber’s movement, comparatively less attention has been given to surrounding-based objectives, where the cops win by occupying all neighbors (or incident edges) of the robber. This notion was recently formalized by Jungeblut et al. [17]. A closely related line of research is the Intruder Capture (IC) problem [3], where the objective is not only to detect but also to capture the intruder in a network. The IC problem has been studied extensively in various network settings (e.g., [4, 10, 13, 14, 19]), and a comprehensive survey is available in [20]. Another related problem is Black Hole Search (BHS) [12], which can be viewed as a static counterpart of infection detection: infected nodes do not propagate the infection, and the goal is to locate such a node while minimizing losses. The problem CLR lies at the confluence of the IC, BHS, and Cops and Robbers paradigms. While IC and BHS have been extensively investigated in distributed settings, the Cops and Robbers game has largely been studied from a centralized graph-theoretic perspective. To the best of our knowledge, distributed variants of pursuit–evasion games of this type have not been explored. Consequently, CLR opens a new avenue for studying pursuit–evasion strategies under distributed computational constraints, such as limited visibility, restricted communication, and incomplete knowledge of the network. 1.3. Preliminaries and notations For a graph G, the cop number c(G) is the smallest integer k such that k cops have a winning strategy against a single robber on G. We now define the notions of boundary vertices, safe zone, and unsafe zone. At any round t, the boundary vertices are the vertices closest to the robber that contain at least one cop. In general, there are exactly two boundary vertices, denoted by bt1 and bt2 . However, if all cops are located at a single vertex, then there is exactly one boundary vertex. The safe zone at round t is the segment of the ring between the boundary vertices, including the 4
boundary vertices, that does not contain the robber. Let Zt denote the set of vertices in the safe zone. Observe that the robber cannot occupy any vertex of the safe zone. Moreover, if |Zt | = n − 1, then the robber is surrounded by the cops. We denote the length of the safe zone as ρ̄, where ρ̄ = |Zt | − 1. The unsafe zone at round t is the segment between the boundary vertices that contains the vertex occupied by the robber. The robber may occupy any vertex of the unsafe zone except the boundary vertices. We denote by ρ the length of the unsafe zone in the initial configuration and define it as ρ = n − ρ̄. Figure 1 illustrates these notions.
Figure 1: A configuration at round t with boundary vertices bt1 and bt2 . The segment St = (bt1 , s1 , s2 , . . . , sj , bt2 ) denotes the safe zone (thin line), while Ut = (u1 , u2 , . . . , uρ−1 ) denotes the unsafe zone (thick line). The filled black circle at ui represents the robber, and a star inside a vertex represents a cop occupying that vertex.
1.4. Our contribution In this work, we introduce the concept of lethal robber and study the Cops and Lethal Robber CLR game on the n-vertex ring Cn in a distributed setting. We first show that c(Cn ) ≥ n + 1 (refer Theorem 2.1). We then present a deterministic distributed algorithm that uses max{ρ + ⌊log ρ⌋ + 4, n − ρ + 4} many cops starting from an arbitrary initial configuration, and successfully surrounds the robber (refer Theorem 4.1). Consequently, c(Cn ) ≤ max{ρ + ⌊log ρ⌋ + 4, n − ρ + 4}. Further, each cop requires O(log n) bits of memory, and the algorithm terminates within O(n3 ) rounds. Our study also connects the IC and BHS problems. In IC, the intruder is dynamic, arbitrarily fast, and its location is unknown, but it is not lethal. In contrast, BHS considers a lethal but static node. Our model combines these two aspects by introducing a dynamic, arbitrarily fast, and lethal adversary, and can thus be viewed as a dynamic variant of BHS, a setting that, to the best of our knowledge, remains unexplored (see Section 5). 2. Impossibility with n cops In this section, we provide an impossibility result for the CLR problem, where n ≥ 4. The intuition behind the result is that the robber, due to its unbounded speed and complete 5
knowledge of the cops’ strategy, can eliminate cops whenever they attempt to expand the safe zone. Consequently, exploring new vertices necessarily incurs losses. Consider an initial configuration in which all n cops are co-located at a single vertex, which is a special case of an arbitrary initial configuration. We analyze how the safe zone evolves as the cops attempt to explore new vertices. First, we bound the rate at which the safe zone can expand. We then show that every such expansion allows the robber to eliminate cops. Finally, combining these observations, we derive a lower bound on the number of cops required to successfully surround the robber. Lemma 2.1. For any even round t, the robber can always restrict the expansion of the safe zone to at most one new vertex in round t + 2. Consequently, |Zt+2 | ≤ |Zt | + 1. Proof. At any even round t, the safe zone can expand only through the boundary vertices bt1 and bt2 . Since each cop can move at most one hop per round, the cops can attempt to expand the safe zone by moving to the vertices adjacent to bt1 and bt2 in the unsafe zone during round t + 2. Thus, they can attempt to add at most two new vertices to the safe zone. If the cops attempt to expand the safe zone from only one boundary vertex, then the statement is immediate. Therefore, suppose they attempt to expand from both boundary vertices. Since the robber has complete knowledge of the deterministic strategy of the cops, at round t + 1 it knows which adjacent unsafe-zone vertices the cops will attempt to occupy from each boundary vertex in round t + 2. The robber then moves to one of these two target vertices. Since the cops do not know the robber’s location, so they execute the same moves, and the cop attempting to enter the occupied vertex is eliminated. Consequently, one of the two expansion attempts fails. Therefore, regardless of the strategy of the cops, the robber can always restrict the expansion of the safe zone to at most one new vertex in round t + 2. Hence, |Zt+2 | ≤ |Zt | + 1. Lemma 2.2. Let the initial configuration be rooted. For any i ∈ [1, n − 3] and any even round t, if |Zt | = i + 1, then by round t, the robber can always eliminate at least i cops. Proof. We prove the statement by induction on i. Base Case: Suppose that for some even round t, we have |Zt | = 2. By Lemma 2.1, there exists an even round t′ ≤ t at which the safe zone expands from one vertex to two vertices. If the cops attempt to expand the safe zone from only one boundary vertex, then the robber moves to the corresponding target vertex and eliminates the cop attempting to enter that vertex. Consequently, the safe zone does not expand. Therefore, to increase the safe zone from one vertex to two vertices, the cops must attempt to expand from both boundary vertices. Since the robber knows the deterministic strategy of the cops, it can move to one of the target vertices and eliminate the cop attempting to enter that vertex in round t′ . Hence, at least one cop is eliminated while the safe zone expands to two vertices. Thus, the statement holds for i = 1. Inductive Step: Let k ∈ [1, n − 4], and assume that whenever |Zr | = k + 1 for some even round r, the robber can eliminate at least k cops by round r. 6
Now consider an even round t such that |Zt | = k + 2. By Lemma 2.1, there exists an even round t′ ≤ t at which the safe zone expands from k + 1 vertices to k + 2 vertices. As in the base case, the cops must attempt to expand from both boundary vertices; otherwise, the robber eliminates the cop attempting to enter the target vertex and the safe zone does not expand. Since the robber knows the deterministic strategy of the cops, it moves to one of the target vertices and eliminates the cop attempting to enter that vertex in round t′ . Thus, one additional cop is eliminated while the safe zone expands from k + 1 to k + 2 vertices. By the induction hypothesis, the robber has already eliminated at least k cops before round t′ . Therefore, by round t, it has eliminated at least k + 1 cops. Hence, by induction, whenever |Zt | = i + 1, the robber can eliminate at least i cops by round t. Lemma 2.3. Let t be an even round such that |Zt | = n − 2 and |Zt+2 | = n − 1. Then, at least four cops must be alive at round t. Proof. Assume, for contradiction, that at most three cops are alive at round t. Since |Zt | = n − 2, the two boundary vertices bt1 and bt2 must each contain at least one cop. Hence, if at most three cops are alive at round t, then besides the cops occupying the boundary vertices bt1 and bt2 , there can be at most one additional cop in the safe zone. If this third cop is not located at a boundary vertex or at a vertex adjacent to a boundary vertex inside the safe zone, then it cannot contribute to the expansion of the safe zone in round t + 2, since each cop can move at most one hop during a cops’ turn. Therefore, without loss of generality, assume that the third cop is positioned either at bt1 or at a vertex adjacent to bt1 inside the safe zone. Now, in order to expand the safe zone from n − 2 vertices to n − 1 vertices in round t + 2, the cops must attempt to occupy a new vertex outside Zt from at least one of the boundary vertices. If the expansion is attempted from bt2 (or from both boundary vertices), then at round t + 1 the robber positions itself on the vertex that a cop from bt2 will attempt to occupy in round t + 2. Since the robber knows the deterministic strategy of the cops, it can predict this movement in advance and eliminate the moving cop in round t + 2. On the other hand, if the expansion is attempted only from bt1 , then the robber similarly positions itself to eliminate the cop moving from bt1 . Thus, in every possible case, the robber can prevent the cops from expanding the safe zone to n − 1 vertices in round t + 2. This contradicts our assumption that at most three cops are alive at round t and yet the safe zone expands to n − 1 vertices in round t + 2. Therefore, at least four cops must be alive at round t. Theorem 2.1. For the CLR problem on Cn with n ≥ 4, we have c(Cn ) ≥ n + 1. Proof. Consider the rooted initial configuration in which all cops are initially located at a single vertex v. Then |Z0 | = 1. To obtain a winning configuration, the cops must eventually reach an even round t such that |Zt | = n − 1. By Lemma 2.1, the cops can expand the safe zone by at most one vertex in each cop’s turn. Hence, before reaching a configuration with |Zt | = n − 1, the cops must first reach 7
a configuration with |Zt | = n − 2. Now, Lemma 2.2, which is proved for the rooted initial configuration, implies that by the time the safe zone expands to n − 2 vertices, at least n − 3 cops can be destroyed. Further, by Lemma 2.3, at least four cops must be alive in order to expand the safe zone from n − 2 vertices to n − 1 vertices. Therefore, the total number of cops required is at least (n − 3) + 4 = n + 1. Hence, c(Cn ) ≥ n + 1. 3. Cops and lethal robber In this section, we present Capture-LR, a deterministic distributed algorithm that surrounds the robber on Cn whenever at least max{ρ + ⌊log ρ⌋ + 4, n − ρ + 4} cops initiate execution from an arbitrary initial configuration, where ρ denotes the length of the unsafe zone in the initial configuration. The cops have no prior knowledge of the robber’s location or each other’s positions. Throughout the paper, whenever we say that a cop performs an action in the next or a subsequent round, we mean the next even-numbered round in which the cops are permitted to move. We now present the high-level idea of the algorithm. High-level idea. Initially the cops are arbitrarily distributed on the ring and have no knowledge of the robber’s location or the boundary of the safe zone. The proposed algorithm proceeds in two steps. In Step 1, the objective is to identify the two boundary vertices of the safe zone and gather all surviving cops at these vertices. To achieve this, the cops collaboratively probe unexplored directions and from the outcomes of these probes, determine whether a direction is safe or leads toward the robber. Whenever both directions from an occupied vertex are verified to be safe, the available cops are redistributed to continue the exploration from other occupied vertices. This process continues until both boundary vertices are identified. At the completion of Step 1, one cop remains at each boundary vertex, while all remaining surviving cops are distributed between these two vertices as evenly as possible. At the beginning of Step 2, every cop computes the same upper bound ρ̂ of the unsafe zone, i.e., ρ̂ ≥ ρ. Step 2 consists of at most h = ⌊log ρ̂⌋ phases. Each phase, except the last, consists of three sub-phases: advancing, checking, and balancing, while the last phase contains only the advancing sub-phase. During the advancing sub-phase, a carefully chosen number of cops simultaneously advance from both boundary vertices into the unsafe zone. The checking sub-phase determines the actual extension achieved on each side and updates the boundary vertices accordingly. Finally, the balancing sub-phase redistributes the remaining cops between the new boundary vertices so that the next phase begins under the same conditions. Repeating this process progressively increases the safe zone until it spans the entire ring, and thereby surrounds the robber. 3.1. Algorithm: Capture-LR In this section we present our algorithm Capture-LR along with the pseudo-codes. Step 1 (Determining the boundary). In Step 1, each cop assumes one of four roles: settler, guard, helper, or checker. The objective is to identify the two boundary vertices of the safe zone. At the completion of this step, exactly two cops serve as guards, 8
one at each boundary vertex, and all remaining alive cops are helpers located at these vertices. Initially, at every occupied vertex, the cop with the minimum identifier assumes the role of settler, while all remaining cops at that vertex, if any, become helpers. Throughout Step 1, every cop c maintains the parameters c.role ∈ {settler, guard, helper, checker} and c.step ∈ {1, 2}, representing its current role and the current step of the algorithm, respectively. In addition, c.ρ̄ stores the length of the safe zone in the initial configuration, and c.N stores the total number of alive cops at the completion of Step 1. Initially, c.step = 1, c.ρ̄ =⊥, and c.N =⊥. Each settler and guard maintain the following parameters for each port p ∈ {0, 1}. The parameter c.saf ep ∈ {⊥, 0, 1} represents the safety status of port p, where ⊥ denotes unknown, 1 denotes safe, and 0 denotes unsafe. The parameter c.checkIDp stores the identifier of the checker assigned to port p, and equals ⊥ when none is assigned. The parameter c.distp ∈ N denotes the current probing distance for port p. The parameter c.timep ∈ N counts the rounds elapsed since the checker assigned to port p last departed from v. Initially, c.saf ep =⊥, c.checkIDp =⊥, c.distp = 0, and c.timep = 0 for both ports. Each checker c maintains two additional parameters: c.distp ∈ N and c.operatorID. The parameter c.distp stores the distance currently being probed through port p, initialized to 1 at the start of each checking task. The parameter c.operatorID stores the identifier of the settler or guard that assigned c to its current checking task, set at assignment and unchanged throughout. Each guard additionally maintains three parameters: c.lead ∈ {⊥, 0, 1}, c.uport ∈ {0, 1, ⊥}, and c.balance ∈ {⊥, 1}, all initialized to ⊥. Upon learning the other guard’s identifier, c sets c.lead ← 1 if its own identifier is smaller, and c.lead ← 0 otherwise. The parameter c.uport stores the port leading toward the unsafe zone from c’s current vertex. The parameter c.balance is set to 1 by the guard with c.lead = 1 once it has confirmed that all surviving cops, except the other guard, have arrived at its vertex. We now define the procedures used in the pseudo-code of Step 1. • Assign(p): A settler or guard c at vertex v executing this procedure selects the minimum-identifier helper at v, say ch , and sets c.checkIDp ← ch .ID, c.distp ← 1, and c.timep ← 0. • MoveTill(p, role): A cop c at vertex v executing this procedure exits through port p and continues in the same direction until it reaches a vertex occupied by a cop c′ with c′ .role = role. • Divide(): Let α denote the number of cops at the current vertex. A cop c executing this procedure exits through port 0 if it is among the ⌈α/2⌉ minimum-identifier cops at the current vertex, and through port 1 otherwise. In either case, it continues in the chosen direction until it reaches a settler or a guard. • Wait(t): A cop c executing this procedure remains idle for t consecutive rounds, including the current round. Equivalently, if c begins executing Wait(t) in round r, it resumes execution of the subsequent statement at the beginning of round r + t. 9
• Check(p, i): A cop c at vertex v executing this procedure traverses through port p, advancing one hop per round until reaching distance i, and then returns to v along the same path. If another cop is encountered during the forward traversal, c immediately returns to v. The parameter c.meetp , initially 0, is set to 1 if such an encounter occurs. • Extended_Check(p, i): A cop c at vertex v executing this procedure behaves as in Check(p, i), except that it records the observed interaction using the parameter c.enctypep , initially 0. The value 0 indicates that no cop, or only a helper or checker, is encountered. The value 1 indicates that a settler currently having, or previously having had, at least one assigned checker is encountered. The value 2 indicates that a settler that has never had an assigned checker is encountered. The value 3 indicates that a guard is encountered, in which case its identifier is stored in c.encID. Throughout the traversal, c sets c.task ← extcheck so that any encountered cop can identify that it is executing this procedure. Algorithm for checker (see Algorithm 1). A checker is a helper temporarily assigned by the settler or the guard to probe a specific direction up to a specific distance. If assigned by the settler, the checker first checks whether the port it is probing has already been marked safe; if so, it reverts to being a helper. Otherwise, it checks whether it encountered another cop during its last probe. If it did, the direction is safe, and the checker reverts to being a helper. If it did not, the checker probes one hop further. If assigned by the guard, the checker probes one hop further each time it returns by incrementing c.distp and executing Extended_Check, unless it met the other guard during its last probe; in that case, it reverts to being a helper. Algorithm 1: Capture-LR : Step 1 (checker) Let c be any cop at vertex v with c.step = 1 and c.role = checker. if a cop cs with cs .checkIDp = c.ID, for some port p, is present at v then 3 if cs .role = settler then 4 if cs .saf ep = 1 then 5 c.role ← helper 6 else 7 if c.meetp = 1 then 8 c.role ← helper 9 else 10 c.distp ← c.distp + 1 and execute Check(p, c.distp ) 1 2
11 12 13 14 15
// cs is a guard
else if c.enctypep ̸= 3 then c.distp ← c.distp + 1 and execute Extended_Check(p, c.distp ) else c.role ← helper
Algorithm for helper (see Algorithm 2). A helper assists the settler or guard at its current vertex v. If both ports of v are confirmed unsafe, the helper moves on to Step 2, and additionally, the minimum-ID helper takes on the role of guard. If both ports of v are confirmed safe, the helper waits for any active checker to return and then 10
Algorithm 2: Capture-LR : Step 1 (helper) Let c be any cop at vertex v with c.step = 1 and c.role = helper. Let cs be the settler or guard at v if cs .saf e0 = 0 and cs .saf e1 = 0 then 3 c.N ← total cops at v, c.ρ̄ ← 0 4 if c is the minimum-ID helper at v then 5 c.lead ← 0, c.uport ← 1, c.role ← guard 6 c.step ← 2 7 else if cs .saf e0 = 1 and cs .saf e1 = 1 then 8 if cs .checkIDp ̸=⊥, for any port p ∈ {0, 1} then 9 remain idle until cs .checkIDp =⊥ 10 execute Divide() 11 else 12 if cs .role = settler then 13 if cs .saf ep =⊥ and cs .checkIDp =⊥ for both p = 0, 1 then 14 if c is the minimum-ID helper present at v then 15 c.role ← checker and execute Check(0, 1) 16 else if c is the second minimum-ID helper present at v then 17 c.role ← checker and execute Check(1, 1) 18 else if cs .saf ep =⊥ and cs .checkIDp =⊥ for exactly one port p then 19 if c is the minimum-ID helper present at v then 20 c.role ← checker and execute Check(p, 1) 21 else 22 if cs .balance = 1 then 23 c.N ← (cops at v ′ ) + 1, c.ρ̄ ← cs .ρ̄ 24 if c is among the ⌈(c.N − 2)/2⌉ minimum-ID helpers then 25 execute Wait(c.ρ̄) 26 else 27 execute MoveTill(1 − cs .uport, guard) 28 c.step ← 2 1
2
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
// not all cops have gathered yet
else
if cs .saf ep =⊥ and cs .checkIDp =⊥ for some port p then if c is the minimum-ID helper present at v then c.role ← checker and execute Extended_Check(p, 1) if a checker cckr is present at v with cckr .portin = p and cckr .task = extcheck then if cckr .operatorID ̸= cs .ID then if cckr .operatorID < cs .ID then execute MoveTill(p, guard) else if cckr .enctypep = 2 then if c is the minimum-ID helper then execute MoveTill(p, settler) else if cckr .enctypep = 3 then if cs .ID > cckr .encID then execute MoveTill(p, guard) if cs .lead = 0 then execute MoveTill(1 − cs .uport, guard)
executes Divide(). If neither condition holds, the helper’s behavior depends on whether it is assisting a settler or a guard. If assisting a settler and exactly one port has unknown safety status and no assigned checker, the minimum-ID helper at v becomes the checker for that port. If both ports satisfy this condition, the minimum-ID and second-minimum-ID helpers become checkers for port 0 and port 1, respectively. If assisting a guard and all surviving cops have already gathered at v (the guard has set balance = 1), the helper learns the total number of surviving cops and the waiting time from the guard. If it is among the smaller-ID half of the helpers, it waits accordingly; otherwise, it moves toward the other guard. Either way, it then moves on to Step 2. If 11
assisting a guard and not all cops have gathered yet (balance is not yet set), the helper does two things. First, if some port has unknown safety status and no assigned checker, the minimum-ID helper at v becomes the checker for that port. Second, the helper reacts when a checker arrives at v. If this checker is probing on behalf of another guard with a smaller identifier than its own guard, the helper moves toward that guard. If instead the checker is probing on behalf of its own guard, the helper checks what it encountered. If the checker met a settler that has never had a checker assigned, the minimum-ID helper moves to assist that settler in probing its remaining port. If the checker met the other guard, which has the smaller identifier of the two guards, or the helper sees that its own guard has already set lead = 0, then the helper moves toward the other guard through the safe zone. Algorithm 3: Capture-LR : Step 1 (settler) Let c be any cop at vertex v with c.step = 1 and c.role = settler. if c.saf e0 = 1 and c.saf e1 = 1 then 3 if c.checkIDp ̸=⊥, for any port p ∈ {0, 1} then 4 remain idle until c.checkIDp =⊥ 5 c.role ← helper
1 2
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
else
// at least one port is not yet confirmed safe if a checker c1 with c1 .portin = p and c1 .ID ̸= c.checkIDp is present at v, for some p ∈ {0, 1} then c.saf ep ← 1 for each port p ∈ {0, 1} satisfying c.checkIDp ̸=⊥ do if a checker c′ with c′ .ID = c.checkIDp and c′ .portin = p is present at v then if c′ .meetp = 1 then c.saf ep ← 1, c.checkIDp ←⊥ else if c′ .meetp = 0 and c.saf ep = 1 then c.checkIDp ←⊥ else if c′ .meetp = 0 and c.saf ep =⊥ then c.distp ← c.distp + 1, c.timep ← 0 else if no checker c′′ satisfying c′′ .ID = c.checkIDp is present at v then if c.timep < 2 · c.distp then c.timep ← c.timep + 1 else c.saf ep ← 0, c.checkIDp ←⊥ if c.checkIDq ̸=⊥, where q = 1 − p then remain idle until c.checkIDq =⊥ c.role ← guard for each port p ∈ {0, 1} in order satisfying c.saf ep =⊥ and c.checkIDp =⊥ do if a helper ch is present at v with ch .ID ̸= c.checkID0 and ch .ID ̸= c.checkID1 then Assign(p)
Algorithm for settler (see Algorithm 3). If any port p has unknown safety status with no assigned checker, and at least one unassigned helper is available at v, the settler assigns the minimum-ID such helper as the checker for port p via Assign(p). If both ports of the settler’s current vertex v are already confirmed safe, it becomes a helper if it has no assigned checker; otherwise, it waits for its assigned checker to return before becoming a helper. Otherwise, if at least one port is still not marked safe, it works as follows. If the settler sees a checker (not its assigned checker) enter through some port p, it marks port p as safe. Otherwise, if its assigned checker returns through port p (within a certain time window, specified later), the settler decides the safety status of port p based on the checker’s report. If the checker encountered another cop during 12
Algorithm 4: Capture-LR : Step 1 (guard) Let c be any cop at vertex v with c.step = 1, c.role = guard, and c.saf eq = 0 for port q. Let p = 1 − q if c.saf e0 = 0 and c.saf e1 = 0 then 3 c.N ← total cops at v, c.ρ̄ ← 0, c.lead ← 1, c.uport ← 0, c.step ← 2 4 else if c.balance = 1 then 5 execute Wait(c.ρ̄) 6 c.step ← 2 7 else 8 if a checker c′ is present at v with c′ .portin = p, c′ .task = extcheck and c′ .ID ̸= c.checkIDp then 9 if c′ .operatorID > c.ID then 10 c.lead ← 1, c.uport ← q, c.ρ̄ ← c′ .distp 11 execute Wait(2 · c.ρ̄) 12 c.N ← (cops at v) + 1, c.balance ← 1 13 else 14 c.lead ← 0, c.uport ← q, c.ρ̄ ← c′ .distp 15 remain idle until a cop c′′ is present at v such that c′′ .N ̸=⊥ 16 c.N ← c′′ .N , c.step ← 2 17 if c.checkIDp =⊥ then 18 if c.lead =⊥ and a helper ch is present at v then 19 execute Assign(p) 1
2
20
// a checker has already been assigned to port p
else
35
if a checker c′ is present at v with c′ .portin = p and c′ .ID = c.checkIDp then if c′ .enctypep = 0 then c.distp ← c.distp + 1, c.timep ← 0 else if c′ .enctypep ∈ {1, 2} then c.timep ← 0 else c.ρ̄ ← c.distp if c.ID < c′ .encID then c.lead ← 1, c.uport ← q execute Wait(2 · c.ρ̄) c.N ← (cops at v) + 1, c.balance ← 1 else c.lead ← 0, c.uport ← q remain idle until a cop c′′ is present at v such that c′′ .N ̸=⊥ c.N ← c′′ .N , c.step ← 2
36
else
21 22 23 24 25 26 27 28 29 30 31 32 33 34
37 38 39 40
// the assigned checker has not yet returned if c.timep < 2 · c.distp then c.timep ← c.timep + 1 else c.saf ep ← 0
probing, the settler marks port p as safe. If no cop was encountered and the port was already confirmed safe, the settler de-assigns the checker from the role of checker for port p. If the safety status of port p is still unknown, the settler increments c.distp and resets c.timep so that the checker probes one step further. If the assigned checker does not return within 2 · c.distp rounds, the settler marks port p as unsafe. It then waits for the assigned checker of the other port, if any, to return, after which the settler transitions to guard. Algorithm for guard (see Algorithm 4). The guard is stationed at a boundary vertex with one unsafe port q and port p = (1 − q) whose safety is unknown. If port p has no assigned checker and guard c has not yet set its lead parameter (c.lead =⊥), it assigns the minimum-ID available helper as the checker for port p. If both ports are marked unsafe, c moves on to Step 2. If all surviving cops have already gathered at its vertex, the 13
guard waits ρ̄ rounds for the helpers to split before moving on to Step 2. If port p is not yet marked unsafe, the guard works as follows. If a checker arrives at v through port p while executing Extended_Check, but it is not the checker assigned by c, then it has come from the other guard’s vertex carrying that guard’s identifier. If this identifier is larger than c’s, c sets c.lead = 1, waits 2 · ρ̄ rounds for all cops to arrive, counts them, and marks that all cops have gathered. Otherwise, c sets c.lead = 0, waits until some cop informs it of the total number of surviving cops, and then moves on to Step 2. If instead c’s assigned checker returns through port p, it decides what to do based on the checker’s report. If the checker met no cop, or met a helper or another checker, c increments c.distp and resets c.timep so that the checker probes one step further. If the checker met the settler, c only resets c.timep so that the checker probes the same distance again. If the checker met the other guard, c decides which of the two guards leads by comparing their identifiers, proceeding exactly as described above, where its action depends on whether its identifier is smaller or larger than the other guard’s identifier. If the assigned checker does not return within 2 · c.distp rounds, c marks port p as unsafe. Step 2 (Expanding the safe zone). At the completion of Step 1, one guard is positioned at each boundary vertex of the safe zone, while all remaining alive cops are helpers distributed between these two vertices. Every cop knows the values of ρ̄ and N computed during Step 1. Let f (x) = x+⌊log x⌋+2. Each cop computes ρ̂ = max{x ∈ N : f (x) ≤ N }, and sets h = ⌊log ρ̂⌋. Step 2 consists of h phases, indexed by i = 1, . . . , h. Each of the first h − 1 phases consists of three sub-phases: advancing, checking, and balancing, while the last phase consists only of the advancing sub-phase, after which the robber is surrounded (see Lemma 4.10). Every cop c maintains the counters c.count1 , c.count2 , c.count3 ∈ N, each initialized to 1 at the beginning of its corresponding sub-phase. At the end of every round of sub-phase j, the counter is updated as c.countj ← c.countj + 1. Thus, c.countj always equals the current round number within sub-phase j and is reset to 1 at the beginning of the next phase. Each helper ch maintains ch .advance ∈ {0, 1, 2}, initially 0. It is set to 1 when the helper enters the unsafe zone during the advancing sub-phase, and to 2 when designated as the messenger by the guard with c.lead = 1, after which it carries the extension information to the other guard through the safe zone. Whenever c.advance = 1, the parameter ch .hops ∈ N stores the number of hops moved by ch into the unsafe zone. At the beginning of each phase i, every cop computes the phase parameters xi , bi , and di . The parameter xi denotes the number of cops advancing from each boundary vertex during the advancing sub-phase, bi is a buffer used to correct rounding when xi−1 is odd, and di denotes the length of the safe zone at the end of phase i. These parameters are
14
initialized as x0 = ρ̂, b0 = 1, and d0 = ρ̄, and are updated as: x i−1 , b if xi−1 is even, i−1 2 xi−1 + 1 , 0 if xi−1 is odd and bi−1 = 1, (xi , bi ) = 2 xi−1 − 1 , 1 if xi−1 is odd and bi−1 = 0, 2
di = di−1 + xi .
(1)
Each guard retains the parameters c.lead, c.uport, and c.saf ep from Step 1, since they correctly identify the boundary and the unsafe direction. The parameters c.checkIDp , c.distp , and c.timep are reset to ⊥, 0, and 0, respectively, at the beginning of Step 2, as the checking process starts afresh. In addition, the guard with c.lead = 1 maintains the parameter c.extend, which is set during the checking sub-phase to the number of hops by which the safe zone is extended on its side. Each checker maintains the parameter c.distp ∈ N, storing the distance currently being probed through port p. Step 2 uses the procedures Assign(p) and MoveTill(p, role) defined in Step 1. In addition, we define the following procedures. • Advance(p, i): A cop c at vertex v executing this procedure exits through port p, moves one hop per round for exactly i rounds, and then remains at the destination vertex. • Advance_Check(p, i): A cop c at vertex v executing this procedure traverses through port p, advancing one hop per round until reaching distance i, and then returns to v along the same path. The parameter c.meetp , initially 0, is set to 1 if another cop is present at the destination vertex. • Balance(): Let α denote the number of helpers at the current vertex. A cop c executing this procedure moves toward the other guard through the safe zone if it is among the ⌊α/2⌋ helpers with the largest identifiers; otherwise, it remains at the current vertex. Algorithm for Sub-phase 1: Advancing (see Algorithm 5). This sub-phase proceeds identically at both boundary vertices. In the first round, the minimum-ID helper departs through the unsafe port. In each subsequent round, the minimum-ID helper currently present at the boundary vertex departs through the same port, while every previously departed helper advances one hop further in the unsafe direction. Thus, over xi rounds, exactly one helper leaves the boundary vertex in each round, and the movement proceeds in a pipelined manner. As a special case, both guards may be located at the same vertex, which occurs only in Phase 1 for a rooted initial configuration. In each round, the minimumID helper departs through the unsafe port of the guard with c.lead = 1, while the secondminimum-ID helper departs through the unsafe port of the other guard. At the end of round xi + 1, all cops set c.subphase ← 2 and begin the next sub-phase in the following round. 15
Algorithm 5: Capture-LR: Step 2, Phase i - Sub-phase 1 (Advancing) Let c be a cop at vertex v with c.step = 2 and c.subphase = 1. if c.role = guard then 3 if c.count1 = xi + 1 then 4 c.subphase ← 2 5 else if c.role = helper then 6 if c.count1 = xi + 1 then 7 c.subphase ← 2 8 else 9 if only one guard c′ is present at v then 10 if c is the minimum-ID helper at v then 11 c.advance ← 1 12 c.hops ← xi − c.count1 + 1 13 execute Advance(c′ .uport, c.hops) 14 else if two guards c1 and c2 are present at v then 15 let c1 be the guard with c1 .lead = 1 16 if c is the minimum-ID helper at v then 17 c.advance ← 1 18 c.hops ← xi − c.count1 + 1 19 execute Advance(c1 .uport, c.hops) 20 else if c is the second minimum-ID helper at v then 21 c.advance ← 1 22 c.hops ← xi − c.count1 + 1 23 execute Advance(c2 .uport, c.hops) 1 2
Algorithm for Sub-phase 2: Checking (see Algorithm 6). This sub-phase determines the extension of the safe zone on both sides. At the vertex of the guard cg with cg .lead = 1, the minimum-ID helper is assigned as the checker for the unsafe port p = cg .uport in the first round. The checker initially probes one hop through the unsafe port and returns, reporting whether the helper stationed there is still present. As long as the reported vertex remains occupied, the checker probes one hop farther than before. This continues until the checker either finds an empty vertex, fails to return in time, or safely probes the full distance xi . In the first case, cg determines the extension of the safe zone on its side, stores it in cg .extend, moves to the new boundary vertex, updates its unsafe port, and instructs the helper stationed there to carry cg .extend through the safe zone to the other guard. The guard c′g with c′g .lead = 0 waits for this helper. Upon its arrival, c′g learns cg .extend and advances xi − cg .extend hops through its unsafe port. Since the maximum time for the helper to arrive is Ti − xi , if it does not arrive within this time, c′g concludes that the safe zone was not extended on the other side and therefore advances the full xi hops on its own side. Thus, the checking sub-phase completes within Ti rounds, and in round Ti + 1,for every cop sets c.subphase ← 3. (see Algorithm 7). This sub-phase gathers Algorithm Sub-phase 3: Balancing all helpers at the vertex of the guard cg with cg .lead = 1, and then redistributes them between the two new boundary vertices. Every helper not already at the vertex of cg moves through the port by which it last entered its current vertex and continues until reaching a guard. If the encountered guard is cg , the helper waits until cg sets cg .balance = 1. Otherwise, it continues through the safe port of the other guard until reaching cg . Within 2di rounds, all helpers gather at the vertex of cg , after which cg sets cg .balance = 1. In the 16
Algorithm 6: Capture-LR: Step 2, Phase i - Sub-phase 2 (Checking) 1
Let c be a cop at vertex v with c.step = 2 and c.subphase = 2, and let Ti = 2(1 + 2 + · · · + xi ) + 2xi + di + 1.
if c.role = guard then 3 let p = c.uport and q = 1 − p 4 if c.count2 = Ti + 1 then 5 c.checkIDp ←⊥, c.subphase ← 3 6 else 7 if c.lead = 1 then 8 if c.checkIDp =⊥ then 9 Assign(p) 10 else 11 if a checker c′ is present at v with c′ .portin = p and c′ .meetp = 1 then 12 if c.distp < xi then 13 c.distp ← c.distp + 1, c.timep ← 0 14 else 15 c.extend ← xi 16 execute Advance(p, xi ) 17 c.uport ← 1 − c.portin 18 remain idle until c.count2 = Ti 19 else if a checker c′ is present at v with c′ .portin = p and c′ .meetp = 0 then 20 c.extend ← c.distp − 1 21 execute Advance(p, c.extend) 22 c.uport ← 1 − c.portin 23 remain idle until c.count2 = Ti 24 else 25 c.timep ← c.timep + 1 26 if c.timep = 2 · c.distp then 27 c.extend ← c.distp − 1 28 execute Advance(p, c.extend) 29 c.uport ← 1 − c.portin 30 remain idle until c.count2 = Ti 31 else 32 if c.count2 ≤ Ti − xi and a helper ch with ch .advance = 2 is present at v then 33 if ch .hops = xi then 34 remain idle until c.count2 = Ti 35 else 36 execute Advance(c.uport, xi − ch .hops) 37 c.uport ← 1 − c.portin 38 remain idle until c.count2 = Ti 39 else if c.count2 = Ti − xi and no helper with advance = 2 is present at v then 40 execute Advance(c.uport, xi ) 41 c.uport ← 1 − c.portin 2
else if c.role = helper then if c.count2 = Ti + 1 then 44 c.subphase ← 3 45 else 46 if c.advance = 0 then 47 if a guard cg with cg .lead = 1 is present at v and cg .checkIDp =⊥ , where p = cg .uport then 48 if c is minimum-ID helper present at v then 49 c.role ← checker, c.distp ← 1 50 execute Advance_Check(p, 1) 51 else if c.advance = 1 then 52 if a guard cg with cg .lead = 1 is present at v and c.hops = cg .extend then 53 c.advance ← 2 54 execute MoveTill(c.portin, guard)
42
43
else if c.role = checker then if c.count2 = Ti + 1 then 57 c.subphase ← 3 58 else 59 if guard cg is present at v and cg .checkIDp = c.ID for some port p then 60 if c.distp ≤ xi then 61 c.distp ← c.distp + 1 62 execute Advance_Check(p, c.distp ) 63 else 64 c.role ← helper, c.advance ← 0 17 65 remain idle until c.count2 = Ti
55
56
Algorithm 7: Capture-LR: Step 2, Phase i - Sub-phase 3 (Balancing) Let c be a cop at vertex v with c.step = 2 and c.subphase = 3. if c.role = guard then 3 if c.count3 = 3di + 1 then 4 c.phase ← i + 1 5 c.subphase ← 1 6 else if c.role = helper then 7 if c.count3 = 3di + 1 then 8 c.phase ← i + 1 9 c.subphase ← 1 10 else 11 if c is at the vertex of guard cg with cg .lead = 1 then 12 remain idle until c.count3 = 2di 13 execute Balance() 14 else 15 execute MoveTill(c.portin, guard) 16 if guard cg is present at v with cg .lead = 0 then 17 execute MoveTill(1 − cg .uport, guard) 1 2
next round, every helper orders itself by identifier. The helpers with the larger identifiers move through the safe zone toward the other guard, while the remaining helpers wait for di rounds, allowing the moving helpers to complete their journey. In the following round, every cop sets c.phase ← i + 1 and c.subphase ← 1. 4. Correctness and complexity analysis In this section we provide the correctness of Capture-LR along with complexity analysis. Lemma 4.1. At most two cops are eliminated during Step 1 of the algorithm Capture-LR. Proof. We first show that only checkers can be eliminated during Step 1. A settler never leaves its current vertex (see Algorithm 3). A guard also remains at its boundary vertex throughout Step 1 and either waits or communicates only with cops arriving at its current vertex (see Algorithm 4). A helper moves only through ports that have already been verified safe, either while executing Divide() (see Algorithm 2, Lines 7–10) or MoveTill() (see Algorithm 2, Lines 22–27 and 37–45). Hence, none of these roles can encounter the robber. The only role that probes unexplored directions is the checker (see Algorithm 1), and therefore only a checker can be eliminated. A checker can be eliminated only while probing through a port whose safety has not yet been determined, and that leads toward the robber. If the assigned checker does not return within the expected time, the corresponding settler or guard marks that port as unsafe. Moreover, if the cop that assigned the checker is a settler, it becomes a guard, if it has not already done so (see Algorithm 3, Lines 17–24, and Algorithm 4, Lines 36– 40). Once a port is marked unsafe, no further checker is assigned to probe through that port (see Algorithm 4). Therefore, each unsafe port can cause at most one checker to be eliminated. Since the ring has exactly two boundary vertices, there are at most two such unsafe ports leading into the unsafe zone. Hence, at most two cops are eliminated during Step 1. 18
Lemma 4.2. For Step 1 of Capture-LR to terminate successfully, the initial configuration must contain either a vertex with at least three cops or at least three distinct vertices each containing at least two cops. Proof. Suppose the initial configuration does not satisfy the stated condition. Then every occupied vertex contains at most two cops, and at most two vertices contain exactly two cops. Consider an initial configuration in which these two vertices are precisely the boundary vertices, and at both vertices, port 0 leads toward the unsafe zone. Each such vertex initially contains one settler and one helper. The settler assigns the helper as a checker to probe port 0 (see Algorithm 3, Lines 25–27). Since both checkers move toward the robber, the robber can eliminate both checkers. Consequently, both settlers mark port 0 as unsafe and become guards (see Algorithm 3, Lines 17–24). At this point, no helper remains at either boundary vertex to continue probing the remaining port or to propagate information through the safe zone. Every other occupied vertex contains only a single settler, which cannot assign a checker. Hence, no further progress is possible, and Step 1 cannot terminate successfully. Therefore, for Step 1 of Capture-LR to terminate successfully, the initial configuration must contain either a vertex with at least three cops or at least three distinct vertices each containing at least two cops. Lemma 4.3. The condition of Lemma 4.2 is always satisfied whenever at least n − ρ + 4 cops are initially available. Proof. Recall that ρ denotes the length of the unsafe zone in the initial configuration. Hence, the cops initially occupy at most n − (ρ − 1) = n − ρ + 1 vertices. Suppose, for contradiction, that the initial configuration does not satisfy the condition of Lemma 4.2. Then at most two occupied vertices contain two cops each, and every other occupied vertex contains exactly one cop. Since the cops occupy at most n − ρ + 1 vertices, the total number of cops is at most 2 · 2 + (n − ρ − 1) · 1 = n − ρ + 3, contradicting the assumption that at least n − ρ + 4 cops are initially available. Therefore, the initial configuration satisfies the condition of Lemma 4.2. Lemma 4.4. At the completion of Step 1, all alive cops possess the same values of the parameters ρ̄ and N , and simultaneously begin the execution of Step 2. Proof. The two guards first discover each other in one of two ways. Either a guard’s assigned checker returns after encountering the other guard (checker c′ returned through port p with parameter c′ .enctypep = 3), or a checker assigned by the other guard arrives at its current vertex. In either case, both guards determine the length of the safe zone as the probing distance of the corresponding checker and store it locally as ρ̄ (see Algorithm 4, Lines 26–27 and 8–10). Thus, both guards obtain the same value of ρ̄. In either case, the guard with the smaller identifier sets lead = 1, and the guard with the larger identifier sets lead = 0 (see Algorithm 4, Lines 8–14 and 26–33). The guard with lead = 1 then executes Wait(2ρ̄), allowing every alive cop, except the other guard, sufficient time to reach its vertex. It then computes the total number of alive cops as 19
N = (cops at its current vertex) + 1 and sets its parameter balance = 1 (see Algorithm 4, Lines 11–12 and 30–31). Every helper at that vertex observes the guard set the parameter balance = 1 and immediately learns the values of ρ̄ and N from the guard (see Algorithm 2, Lines 22– 23); this happens for all such helpers before any of them move. Only afterward are the helpers divided into two groups by identifier: the ⌈(N − 2)/2⌉ helpers with the smaller identifiers remain at the current vertex and execute Wait(ρ̄), while the remaining helpers, already carrying the values of ρ̄ and N , move toward the other guard through the safe zone (see Algorithm 2, Lines 24–27). Since the length of the safe zone is ρ̄, this journey takes exactly ρ̄ rounds. Correspondingly, the guard with lead = 1 itself executes Wait(ρ̄) once balance = 1 is set, before proceeding to Step 2 (see Algorithm 4, Lines 4–6). Hence, the guard with lead = 1 and the helpers that remain at its vertex both become ready for Step 2 exactly ρ̄ rounds after its parameter balance is set to 1 — precisely when the departing helpers complete their journey through the safe zone. Meanwhile, the guard with lead = 0 remains idle until some cop with a known value of N arrives at its vertex (see Algorithm 4, Lines 15 and 34); this is precisely the moment when the departing helpers arrive, already carrying the correct value of N . Upon this arrival, the guard with lead = 0 sets its own N accordingly and proceeds to Step 2 (see Algorithm 4, Lines 16 and 35). Therefore, every alive cop possesses the same values of ρ̄ and N , and all alive cops begin the execution of Step 2 simultaneously. Lemma 4.5. If at least ρ + ⌊log ρ⌋ + 2 cops initiate Step 2 of Capture-LR, then every cop can uniquely determine a value ρ̂ satisfying ρ̂ ≥ ρ. Proof. By Lemma 4.4, every alive cop knows the same value of N at the beginning of Step 2. Let f (x) = x + ⌊log x⌋ + 2, and consider the set X = {x ∈ N : f (x) ≤ N }. Since at least ρ + ⌊log ρ⌋ + 2 cops initiate Step 2, we have N ≥ ρ + ⌊log ρ⌋ + 2 = f (ρ). Hence, ρ ∈ X, implying that the set X is non-empty. Furthermore, f is a strictly increasing function. Also, for any fixed value of N , there are only finitely many integers x satisfying f (x) ≤ N . Therefore, the set X has a unique maximum element. Every cop computes ρ̂ = max X. Since every cop knows the same value of N , they all construct the same set X and consequently compute the same value of ρ̂. Finally, because ρ ∈ X and ρ̂ = max X, this implies ρ̂ ≥ ρ. Lemma 4.6. Throughout the execution of Step 2 of Capture-LR, the number of helpers that leave the boundary vertices and move toward the unsafe zone during the advancing sub-phases is at most ρ̂ + 1. Proof. In the advancing sub-phase of every phase i ≥ 1, xi helpers from each boundary vertex set advance = 1 and leave the boundary vertices, moving one by one toward the unsafe zone in a pipe-lined manner (see Algorithm 5, Lines 9–23). Thus, a total of 2xi helpers leave the boundary vertices during the advancing sub-phase of phase i. We refer to these helpers as the advancers of phase i, and to their movement as the advancing task of phase i. 20
Since the cops and the robber move in alternating rounds, the robber remains stationary during each round in which the cops move. The advancing task proceeds simultaneously from both boundary vertices. If the robber is not surrounded, then cops cannot occupy both neighboring vertices of the robber simultaneously. Since a cop can be eliminated only when it moves onto the robber’s current vertex, cops advancing from at most one side can be eliminated in any round of the advancing task. Hence, among the 2xi advancers of phase i, at most xi are eliminated, and at least xi remain alive at the end of the advancing sub-phase of phase i. We refer to these remaining advancers as the surviving advancers of phase i. Recall the recursive definition of xi and bi from Equation (1). Initially, x0 = ρ̂ and b0 = 1. Thereafter, for every phase i ≥ 1, x i−1 , b , if xi−1 is even, i−1 2 xi−1 + 1 , 0 , if xi−1 is odd and bi−1 = 1, (xi , bi ) = 2 x − 1 i−1 , 1 , if xi−1 is odd and bi−1 = 0. 2 Let 0 ≤ j1 < j2 < · · · < jm ≤ h, for some m ≥ 0, denote all indices for which xjp is odd, where p ∈ {1, 2, . . . , m}. For every 1 ≤ i ≤ j1 , we have xi = xi−1 /2 and bi = 1. Hence, 2x1 = ρ̂, 2x2 = x1 , . . . , 2xj1 = xj1 −1 . Therefore, for every 2 ≤ i ≤ j1 , the advancing task of phase i is performed entirely by the surviving advancers of phase i − 1. Consequently, only the initial ρ̂ advancers have ever left the boundary vertices during the advancing sub-phases up to and including phase j1 . Thus, at the end of phase j1 , at least xj1 surviving advancers of phase j1 remain alive. For phase i = (j1 + 1), since xj1 is odd and bj1 = 1, we have xj1 +1 = (xj1 + 1)/2 and bj1 +1 = 0. Hence, 2xj1 +1 = xj1 + 1. Therefore, the advancing task of phase (j1 + 1) is performed by the xj1 surviving advancers of phase j1 together with one additional helper that has not previously left a boundary vertex during any advancing sub-phase. Thus, at the end of phase (j1 + 1), at most ρ̂ + 1 helpers have ever left the boundary vertices during the advancing sub-phases, among which at least xj1 +1 remain as the surviving advancers of phase (j1 + 1). For every j1 + 2 ≤ i ≤ j2 , we have xi−1 even and hence 2xi = xi−1 and bi = bi−1 = 0. Therefore, for every such phase, the surviving advancers of phase (i − 1) exactly suffice to perform the advancing task of phase i. Hence, at the end of phase j2 , at least xj2 surviving advancers of phase j2 remain alive among the previously accounted ρ̂ + 1 helpers. For phase i = (j2 + 1), since xj2 is odd and bj2 = 0, we have xj2 +1 = (xj2 − 1)/2 and bj2 +1 = 1. Hence, 2xj2 +1 = xj2 − 1. Therefore, the advancing task of phase (j2 + 1) is performed by only xj2 − 1 of the xj2 surviving advancers of phase j2 . Consequently, one of these surviving advancers does not participate in the advancing task and remains unused. Hence, at the end of phase (j2 + 1), exactly xj2 +1 surviving advancers of phase (j2 + 1), together with the one unused cop, remain among the previously accounted ρ̂ + 1 helpers. 21
For every j2 + 2 ≤ i ≤ j3 , we have xi−1 even and hence 2xi = xi−1 and bi = bi−1 = 1. Therefore, for every such phase, the surviving advancers of phase (i − 1) exactly suffice to perform the advancing task of phase i. Hence, at the end of phase j3 , exactly xj3 surviving advancers of phase j3 , together with the one unused cop, remain among the previously accounted ρ̂ + 1 helpers. The above argument extends similarly to the remaining phases. More precisely, for every j2q−1 + 2 ≤ i ≤ j2q , where q ≥ 1 and j2q exists, we have xi−1 even and hence 2xi = xi−1 and bi = bi−1 = 0. Therefore, for every such phase, the surviving advancers of phase (i − 1) exactly suffice to perform the advancing task of phase i. Hence, at the end of phase j2q , exactly xj2q surviving advancers of phase j2q remain alive. For phase i = (j2q + 1), since xj2q is odd and bj2q = 0, we have xj2q +1 = (xj2q − 1)/2 and bj2q +1 = 1. Hence, 2xj2q +1 = xj2q − 1. Therefore, one of the surviving advancers of phase j2q does not participate in the advancing task of phase (j2q + 1) and remains unused. For every j2q +2 ≤ i ≤ j2q+1 , where j2q+1 exists, we have xi−1 even and hence 2xi = xi−1 and bi = bi−1 = 1. Therefore, for every such phase, xi of the surviving advancers of phase (i − 1) suffice to perform the advancing task of phase i. Hence, at the end of phase j2q+1 , exactly xj2q+1 surviving advancers of phase j2q+1 , together with the previously unused cop, remain among the previously accounted ρ̂ + 1 helpers. Finally, for phase i = (j2q+1 + 1), since xj2q+1 is odd and bj2q+1 = 1, we have xj2q+1 +1 = (xj2q+1 + 1)/2 and bj2q+1 +1 = 0. Hence, 2xj2q+1 +1 = xj2q+1 + 1. Therefore, the previously unused advancer together with xj2q+1 of the surviving advancers of phase j2q+1 provide the 2xj2q+1 +1 helpers required for the advancing task of phase (j2q+1 + 1). Consequently, throughout the execution of Step 2, the total number of helpers that ever leave the boundary vertices and move toward the unsafe zone during the advancing sub-phases is at most ρ̂ + 1. Lemma 4.7. If at least ρ + ⌊log ρ⌋ + 2 cops initiate Step 2, then at the beginning of every checking sub-phase of Step 2, there exists at least one helper at the vertex occupied by the guard cg with cg .lead = 1. Proof. Recall that N denotes the number of cops initiating Step 2. By Lemma 4.5, since at least ρ + ⌊log ρ⌋ + 2 cops initiate Step 2, every cop determines the same value ρ̂ ≥ ρ satisfying N ≥ ρ̂ + ⌊log ρ̂⌋ + 2. Among the N cops initiating Step 2, exactly two are guards. Hence, there are N − 2 helpers. By Lemma 4.6, at most ρ̂ + 1 helpers ever leave the boundary vertices and move toward the unsafe zone during the advancing sub-phases of Step 2. Therefore, at least (N − 2) − (ρ̂ + 1) ≥ ⌊log ρ̂⌋ − 1 helpers never leave the boundary vertices during any advancing sub-phase. We refer to these helpers as non-advancers. Step 2 consists of h = ⌊log ρ̂⌋ phases, and only the first h − 1 = ⌊log ρ̂⌋ − 1 phases contain a checking sub-phase. During each checking sub-phase, exactly one helper changes its role to checker and executes the procedure Advance_Check, in which it moves into the unsafe zone (see Algorithm 6). Therefore, at most one non-advancer can be eliminated during each checking sub-phase. Since there are ⌊log ρ̂⌋ − 1 non-advancers and the same number of checking sub-phases, at least one non-advancer is alive at the beginning of 22
every checking sub-phase. Therefore, it remains to show that at least one non-advancer is present at the vertex occupied by the guard cg with cg .lead = 1 at the beginning of every checking sub-phase. At the completion of Step 1 and after every balancing sub-phase thereafter, all alive helpers are distributed between the two boundary vertices as evenly as possible. If the number of alive helpers is odd, the boundary vertex occupied by the guard cg with cg .lead = 1 receives one additional helper (see Algorithm 7). Hence, at least one nonadvancer is present at the vertex occupied by cg at the beginning of every checking subphase. Therefore, at the beginning of every checking sub-phase of Step 2, there exists at least one helper at the vertex occupied by the guard cg with cg .lead = 1. Lemma 4.8. Throughout the execution of Step 2, all alive cops execute every phase and every corresponding sub-phase synchronously. Proof. By Lemma 4.4, all alive cops initiate Step 2 simultaneously with identical values of ρ̄ and N . Therefore, by Lemma 4.5, every alive cop determines the same value of ρ̂. Consequently, every alive cop computes identical values of h, xi , bi , and di for every phase i, since these values depend only on ρ̂ (see Equation (1)). Consider phase 1. The duration of each sub-phase depends only on the values of x1 and d1 , which are identical for all alive cops. In particular, every alive cop executes the advancing, checking, and balancing sub-phases for exactly x1 + 1, 2(1 + 2 + · · · + x1 ) + 2x1 + d1 + 2, and 3d1 + 1 rounds, respectively, irrespective of its role during the execution. Since all alive cops start each sub-phase simultaneously and execute it for the same number of rounds, they complete each sub-phase simultaneously. Therefore, all alive cops complete phase 1 together and start phase 2 in the same round. Now suppose that, for some i ≥ 2, all alive cops start Phase i simultaneously. Since every alive cop possesses the same values of xi and di , the duration of every sub-phase of phase i is identical for all alive cops. By the same argument, all alive cops complete each sub-phase of phase i simultaneously and hence start phase i + 1 simultaneously. Therefore, by induction, throughout the execution of Step 2, all alive cops execute every phase and every corresponding sub-phase synchronously. P Lemma 4.9. Define Sk = ki=1 xi , where xi is defined by Equation (1). Then Sh ≥ ρ̂ − 1 for h = ⌊log ρ̂⌋. Proof. We first derive an explicit expression for Sh using the recurrence in Equation (1), and then obtain the required bound. Let 0 ≤ j1 < j2 < · · · < jm ≤ h be the indices such that xjℓ is odd for all ℓ ∈ {1, 2, . . . , m}. Since j1 is the first such index, for all 0 ≤ i ≤ j1 , we have xi = 2ρ̂i and bi = 1. Hence, P 1 ρ̂ Sj1 = ji=1 . 2i x +1 At index j1 , the value xj1 is odd and bj1 = 1, so xj1 +1 = j12 and bj1 +1 = 0. Expanding, 23
ρ̂
1 , + 2j1 +1 2 1 ρ̂ xj1 +2 = j1 +2 + 2 , 2 2 ρ̂ 1 xj1 +3 = j1 +3 + 3 , 2 2 .. . xj1 +1 =
(2) (3) (4) (5)
1 Thus, for all j1 < i ≤ j2 , xi = 2ρ̂i + 2i−j , and bi = 0. Hence, 1 j2 X ρ̂
j2 −j1
X 1 + . 2i 2i i=1 i=1
Sj2 =
At index j2 , the value xj2 is odd and bj2 = 0, so xj2 +1 = ρ̂
xj2 −1 and bj2 +1 = 1. Expanding, 2
1
1 − , 2 1 ρ̂ 1 xj2 +2 = j2 +2 + j2 +2−j1 − 2 , 2 2 2 ρ̂ 1 1 xj2 +3 = j2 +3 + j2 +3−j1 − 3 , 2 2 2 .. . xj2 +1 =
2j2 +1
+
2j2 +1−j1
1 1 − 2i−j , and bi = 1. Hence, Thus, for all j2 < i ≤ j3 , xi = 2ρ̂i + 2i−j 1 2 j3 −j1 3 −j2 X 1 jX 1 + − . i i i 2 2 2 i=1 i=1 i=1
j3 X ρ̂
Sj3 = Proceeding similarly, we obtain Sh =
i=1
h−j2
h−j1
h X ρ̂
2i
X 1
+
2i
i=1
−
X 1 i=1
2i
h−jm
+ · · · + (−1)m+1
X 1 i=1
!
2i
(6)
Since j1 < j2 < · · · < jm , we have h − j1 > h − j2 > · · · > h − jm , and hence h−j1
X 1
h−j2
h−jm
X 1
X 1 ≥ ≥ · · · ≥ . 2i 2i 2i i=1 i=1 i=1
Therefore, h−j1
X 1 i=1
2i
h−j2
−
X 1 i=1
2i
h−j3
+
X 1 i=1
2i
h−jm m+1
− · · · + (−1)
X 1 i=1
24
2i
! ≥ 0.
(7)
P Hence, from Equations (6) and (7), we obtain Sh ≥ hi=1 2ρ̂i . Since h = ⌊log ρ̂⌋, we have P 2h ≤ ρ̂ < 2h+1 , and hence 2ρ̂h < 2. Therefore, hi=1 2ρ̂i = ρ̂ 1 − 21h > ρ̂ − 2. It follows that P Sh > ρ̂ − 2. Since Sh = hi=1 xi and each xi is an integer, Sh is also an integer. Therefore, Sh ≥ ρ̂ − 1, proving the lemma. Lemma 4.10. Step 2 of Capture-LR can be executed successfully, and the robber is surrounded, whenever at least ρ + ⌊log ρ⌋ + 2 cops initiate Step 2. Proof. Recall that N denotes the number of cops initiating Step 2. By Lemma 4.5, since at least ρ + ⌊log ρ⌋ + 2 cops initiate Step 2, every cop determines the same value ρ̂ ≥ ρ satisfying N ≥ ρ̂ + ⌊log ρ̂⌋ + 2 = f (ρ̂). By Lemma 4.6, at most ρ̂ + 1 helpers ever leave the boundary vertices and move toward the unsafe zone during the advancing subphases of Step 2. This bound already accounts for any cops eliminated by the robber while advancing. In addition, there are ⌊log ρ̂⌋ − 1 checking sub-phases, and at most one cop, namely the one acting as the checker, may be eliminated in each checking subphase; no cop is eliminated during any balancing sub-phase. Two cops permanently remain guards throughout Step 2. Hence, the total number of cops required throughout Step 2 is (ρ̂ + 1) + (⌊log ρ̂⌋ − 1) + 2 = ρ̂ + ⌊log ρ̂⌋ + 2 = f (ρ̂). Since N ≥ f (ρ̂), at least this many cops initiate Step 2. By Lemma 4.7, a helper is always available at the vertex of the guard with cg .lead = 1 at the beginning of every checking sub-phase. Hence, every checking sub-phase has a helper available to act as the checker. By Lemma 4.8, all alive cops execute every phase and every corresponding sub-phase synchronously. Therefore, Step 2 never stalls and executes successfully to completion. It remains to show that the robber is surrounded upon the completion of Step 2. At the completion of Step 1, the safe zone contains n − ρ + 1 vertices. Suppose, for the sake of contradiction, that the robber is not surrounded upon the completion of Step 2. In the advancing sub-phase of every phase i ≥ 1, xi helpers from each boundary vertex move simultaneously toward the unsafe zone (see Algorithm 5, Lines 9–23). Since the robber can eliminate helpers on at most one side in each round, at least xi helpers survive the advancing sub-phase. Thus, the size of the safe zone increases by at least xi during phase i, and therefore by at least Sh over the h advancing sub-phases. By Lemma 4.9, Sh ≥ ρ̂ − 1. Since ρ̂ ≥ ρ, we have Sh ≥ ρ − 1. Thus, after the h advancing sub-phases, the safe zone contains at least n − ρ + 1 + (ρ − 1) = n vertices. Therefore, the safe zone covers the entire ring, which implies that the robber is surrounded, a contradiction. Hence, the robber is surrounded upon the completion of Step 2. Lemma 4.11. Algorithm Capture-LR requires O(log n) bits of memory per cop and surrounds the robber within O(n3 ) rounds. Proof. During the execution of Capture-LR, cops with different roles maintain parameters corresponding to ports, counters, distances, phase variables, and synchronization variables. All such parameters, except those storing cop IDs, take values bounded by a polynomial in n. Hence, each such parameter requires at most O(log n) bits of memory. Certain 25
parameters, such as checkID, encID, and operatorID, store cop IDs. Since each cop ID belongs to the range [1, nλ ] for some constant λ, storing such an ID also requires O(log n) bits of memory. Moreover, throughout the execution of the algorithm, each cop maintains only a constant number of parameters. Therefore, the total memory required per cop is O(log n) bits. We now analyze the time complexity of the algorithm. We first analyze the number of rounds required for the completion of Step 1. During Step 1, a checker executes either the Check or the Extended_Check procedure (see Algorithms 1 and 2). Since cops have bounded speed and can move at most one hop in each round, a checker exploring up to distance i requires O(i) rounds. For a settler located at a non-boundary vertex of the safe zone, the cumulative number of rounds spent in all checking procedures before both corresponding ports are marked safe is O((n−ρ)2 ), since the length of the safe zone is n−ρ. Once both ports are marked safe, all the cops present at that vertex, together with the assigned checkers, become helpers and move towards the encountered settlers, which requires at most O(n − ρ) further rounds. Upon reaching another settler, a helper may again be assigned as a checker and repeat the checking process from distance 1. Since at most n − ρ − 1 non-boundary vertices of the safe zone can give rise to such a checkingand-redistribution process, the total number of rounds contributed across all of them is O((n − ρ)3 ). At the two boundary vertices of the safe zone, the corresponding settlers eventually become guards. Their checking procedures may explore both the safe and unsafe zones. Since the total length of the ring is n, the cumulative number of rounds spent in all such checking procedures is bounded by O(n2 ). Moreover, the corresponding redistribution procedures require at most O(n−ρ) rounds. Hence, the total number of rounds contributed by the two boundary vertices is O(n2 + n − ρ) = O(n2 ). Therefore, the total number of rounds required for the completion of Step 1 is O((n − ρ)3 ) + O(n2 ) = O(n3 ). We now analyze Step 2. By Lemma 4.5, every cop computes a value ρ̂ ≥ ρ and h = ⌊log ρ̂⌋ at the start of Step 2. For each phase i ∈ {1, . . . , h}, the advancing sub-phase requires exactly xi +1 rounds, the checking sub-phase requires 2(1+2+· · ·+xi )+2xi +di +2 rounds, and the balancing sub-phase requires exactly 3di + 1 rounds. Hence, the total number of rounds required in phase i is (xi +1)+ 2(1+2+· · ·+xi )+2xi +di +2 +(3di +1). Since 2(1 + 2 + · · · + xi ) = xi (xi + 1) for every 1 ≤ i ≤ h, the number of rounds required to complete phase i is O(x2i + di ). Observe that ρ̂ is computed solely from N , the number of cops that initiate Step 2. Since N is independent of the ring size n, ρ̂ may be either smaller or larger than 2n. Therefore, we distinguish the following two cases. Case 1 (ρ̂ ≥ 2n). By Equation (1), x1 ≥ ρ̂/2 ≥ n. Thus, during the advancing sub-phase of the first phase, more than n cops advance consecutively from each boundary vertex of the safe zone. Consequently, irrespective of the initial configuration, the advancing cops traverse the entire unsafe zone, and hence occupy both neighbors of the robber before the first advancing sub-phase terminates. Hence, the robber is surrounded within the first n rounds of Step 2. Therefore, the cops surround the robber within O(n3 ) + O(n) = O(n3 ) rounds. 26
Case 2 (ρ̂ < 2n). Since ρ̂ = O(n), by Equation (1), xi ≤ (xi−1 + 1)/2 and di = di−1 + xi , where x0 = ρ̂ and d0 = ρ̄. Hence, xi = O(n) and di = O(n) for every phase i ∈ {1, 2, . . . , h}. Therefore, the number of rounds required to complete each phase i is O(x2i + di ) = O(n2 + n) = O(n2 ). Moreover, since h = ⌊log ρ̂⌋, we have h = O(log n). By Lemma 4.10, Step 2 executes successfully and surrounds the robber. Since Step 2 consists of h phases, the robber is surrounded within at most h phases. Hence, Step 2 completes within O(n2 log n) rounds. Therefore, the cops surround the robber within O(n3 ) + O(n2 log n) = O(n3 ) rounds. Hence, in both cases, the cops surround the robber within O(n3 ) rounds. Theorem 4.1. Let n ≥ 4, and let ρ denote the length of the unsafe zone in the initial configuration. Starting from any arbitrary initial configuration on the ring Cn , if at least max{ρ + ⌊log ρ⌋ + 4, n − ρ + 4} cops, each equipped with O(log n) bits of memory, execute the algorithm Capture-LR, then the robber is surrounded within O(n3 ) rounds. Proof. Let k denote the number of cops initially available. By Lemmas 4.2 and 4.3, Step 1 of Capture-LR executes successfully whenever k ≥ n − ρ + 4. Further, by Lemma 4.10, Step 2 of Capture-LR executes successfully and the robber is surrounded whenever at least ρ + ⌊log ρ⌋ + 2 cops initiate Step 2. Since, by Lemma 4.1, at most two cops are eliminated during Step 1, at least k − 2 cops remain alive at the beginning of Step 2. Hence, Step 2 executes successfully and the robber is surrounded whenever k − 2 ≥ ρ + ⌊log ρ⌋ + 2, that is, whenever k ≥ ρ + ⌊log ρ⌋ + 4. Therefore, Capture-LR successfully surrounds the robber whenever k ≥ max{ρ + ⌊log ρ⌋ + 4, n − ρ + 4}. Finally, by Lemma 4.11, Capture-LR requires O(log n) bits of memory per cop, and the cops surround the robber within O(n3 ) rounds. Remark 4.1. The rooted initial configuration is the worst-case arbitrary initial configuration for Capture-LR, requiring n + ⌊log n⌋ + 4 cops to successfully surround the robber. 5. Discussion and conclusion In the classical Black Hole Search (BHS) problem, the black hole is modeled as a static dangerous vertex: any mobile entity entering that vertex is immediately destroyed. A natural extension of this model is to consider a lethal mobile entity that can move through the graph over time. In this setting, if a movable resource and the lethal entity attempt to move to the same vertex during a round, then the resource is destroyed. Hence, compared to the classical black hole, the mobile lethal entity possesses additional power due to its mobility. If such an entity is allowed to move freely forever, then mobile entities may continue to be destroyed indefinitely. Therefore, rather than only detecting the dangerous entity, a more meaningful objective is to capture or block its movement. Observe that the lethal mobile entity can be interpreted as a robber with destructive capability. Suppose we assign all the powers of the lethal entity to the robber in the CLR model. In our setting, each round consists of two phases: first, the robber moves, and then the cops move. If these two phases are viewed together as a single synchronized round, then the robber behaves 27
exactly as a mobile lethal entity. Indeed, whenever one or more cops attempt to move to the same vertex as the robber during that round, the cops are eliminated. Consequently, our CLR algorithm can also be interpreted as an algorithm for capturing a lethal mobile entity. The correctness of the strategy follows from the fact that the cops progressively restrict the movement of the robber until capture becomes inevitable. Hence, our algorithm provides a method for safely capturing a movable black-hole-like entity using mobile resources. The immediate open directions include trying for an algorithm with less number of cops and/or providing a better impossibility result. References [1] Martin Aigner and Michael Fromme. A game of cops and robbers. Discrete Applied Mathematics, 8(1):1–12, 1984. [2] William Baird and Anthony Bonato. Meyniel’s conjecture on the cop number: a survey, 2013. URL: https://arxiv.org/abs/1308.3385, arXiv:1308.3385. [3] Lali Barrière, Paola Flocchini, Pierre Fraigniaud, and Nicola Santoro. Capture of an intruder by mobile agents. In Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’02, page 200–209, 2002. [4] Lélia Blin, Pierre Fraigniaud, Nicolas Nisse, and Sandrine Vial. Distributed chasing of network intruders. Theoretical Computer Science, 399(1):12–37, 2008. [5] Anthony Bonato. The game of cops and robbers on graphs. American Mathematical Soc., 2011. [6] Anthony Bonato, Stephen Finbow, Przemysław Gordinowicz, Ali Haidar, William B Kinnersley, Dieter Mitsche, Paweł Prałat, and Ladislav Stacho. The robber strikes back. In Computational Intelligence, Cyber Security and Computational Models: Proceedings of ICC3, 2013, pages 3–12. Springer, 2013. [7] Peter Bradshaw and Seyyed Aliasghar Hosseini. Surrounding cops and robbers on graphs of bounded genus, 2019. URL: https://arxiv.org/abs/1909.09916, arXiv: 1909.09916. [8] Andrea C Burgess, Rosalind A Cameron, Nancy E Clarke, Peter Danziger, Stephen Finbow, Caleb W Jones, and David A Pike. Cops that surround a robber. Discrete Applied Mathematics, 285:552–566, 2020. [9] Danny Crytser, Natasha Komarov, and John Mackey. Containment: a variation of cops and robber. Graphs and Combinatorics, 36(3):591–605, 2020. [10] Dariusz Dereniowski. Connected searching of weighted trees. Theoretical Computer Science, 412(41):5700–5713, 2011. 28
[11] Anders Dessmark, Pierre Fraigniaud, Dariusz R Kowalski, and Andrzej Pelc. Deterministic rendezvous in graphs. Algorithmica, 46(1):69–96, 2006. [12] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Mobile search for a black hole in an anonymous ring. In Distributed Computing, pages 166–179, 2001. [13] Paola Flocchini, Miao Jun Huang, and Flaminia L. Luccio. Decontamination of hypercubes by mobile agents. Networks, 52(3):167–178, 2008. [14] Fedor V Fomin, Dimitrios M Thilikos, and Ioan Todinca. Connected graph searching in outerplanar graphs. Electronic Notes in Discrete Mathematics, 22(213-216):7th, 2005. [15] Arthur S Goldstein and Edward M Reingold. The complexity of pursuit on a graph. Theoretical computer science, 143(1):93–112, 1995. [16] Paul Jungeblut, Samuel Schneider, and Torsten Ueckerdt. Cops and robber-when capturing is not surrounding. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 403–416. Springer, 2023. [17] Paul Jungeblut, Samuel Schneider, and Torsten Ueckerdt. Cops and robber-when capturing is not surrounding. The Electronic Journal of Combinatorics, pages P3–28, 2025. [18] H. Meyniel. Meyniel’s conjecture on the cop number. Unpublished manuscript, 1985. [19] Nicolas Nisse. Connected graph searching in chordal graphs. Discrete Applied Mathematics, 157(12):2603–2610, 2009. Second Workshop on Graph Classes, Optimization, and Width Parameters. [20] Nicolas Nisse. Network Decontamination. 2019. [21] Richard Nowakowski et al. Cops and Robbers on Graphs. American Mathematical Society, 2019. [22] Richard Nowakowski and Peter Winkler. Vertex-to-vertex pursuit in a graph. Discrete Mathematics, 43(2-3):235–239, 1983. [23] Alain Quilliot. Jeux et points fixes sur les graphes. PhD thesis, Université de Paris VI, 1978. [24] Samuel Schneider. Surrounding cops and robbers, 2022. URL: https://i11www.iti. kit.edu/_media/teaching/theses/ba_schneider22.pdf.
29