PaperlayerView exact revision on arXiv

Source-linked AI summary

Cops and Lethal Robber on Rings: A Distributed Perspective

Amanpreet Singh Saini, Ashish Saxena, Kaushik Mondal

arXiv:2609.06388v1cs.DC

TL;DR

The paper examines how cops can contain a fast robber that can destroy cops entering its vertex, under a model that also restricts the robber from entering cop-occupied vertices. It analyzes a distributed surrounding strategy from arbitrary initial configurations; for Step 1 to terminate, the initial configuration must meet a specific occupancy condition.

  • Problem

    The paper studies containment when a fast robber can destroy cops that enter its vertex, creating a lethal pursuit setting.

    Source: §1 · p. 2

  • Method

    It analyzes a distributed strategy for surrounding the robber from arbitrary initial configurations, with checkers probing unexplored directions while other roles avoid encountering the robber.

    Source: §1.1 · p. 3, §4 · p. 18

  • Results

    Step 1 of Capture-LR can terminate successfully only if the initial configuration has a vertex with at least three cops or at least three distinct vertices each containing at least two cops.

    Source: §4 · p. 19

  • Takeaways & Limitations

    The strategy progressively restricts the robber’s movement until capture becomes inevitable, and can be interpreted as capturing a lethal mobile entity.

    Source: §5 · p. 28

    The model is confined to rings and forbids the robber from moving onto vertices occupied by cops.

    Source: §1 · p. 2, §1.1 · p. 3

Abstract

from arXiv · show

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 {\it 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 {\it 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+\lfloor\log n \rfloor+4$ cops in the worst case.

1. Introduction

The paper defines a distributed cops-and-lethal-robber game in which cops must surround an unknown, fast robber that can destroy cops entering its vertex. On rings, it studies the model’s relation to pursuit-evasion and lethal-environment problems and gives a deterministic strategy with a stated cop bound.

1. Introduction

  • Unlike safe-interaction models, CLR destroys every cop that moves onto the robber, while forbidding the robber from moving onto cop-occupied vertices.The paper contrasts this with a related variant where a robber entering a vertex with multiple cops eliminates only one of them.Source: §1 · p. 2

1.2. Related work

  • CLR combines pursuit of an arbitrarily fast intruder with a lethal entity akin to the static black hole, in a distributed pursuit-evasion setting the authors say was unexplored.The related problems have been studied in distributed settings, while Cops and Robber has largely been studied from a centralized graph-theoretic perspective.Source: §1 · p. 2, §1.2 · p. 4

1.1. Model and the problem definition

  • On an anonymous, port-labeled ring, arbitrarily placed cops lack knowledge of the ring size, other cops’ positions, and the robber’s location, and must guarantee surrounding.The robber has unbounded speed, moves in odd rounds, and the cops move in even rounds.Source: §1.1 · pp. 2–3

1.3. Preliminaries and notations

  • The safe zone is the ring segment between the boundary vertices that excludes the robber, while the unsafe zone contains it; a safe zone of n−1 vertices means the robber is surrounded.Boundary vertices are the vertices closest to the robber that contain cops.Source: §1.3 · pp. 4–5

1.4. Our contribution

  • For Cn, the paper proves c(Cn) ≥ n+1 and gives a deterministic arbitrary-start algorithm using max{ρ+⌊log ρ⌋+4, n−ρ+4} cops, O(log n) bits per cop, and O(n3) rounds.Source: §1.4 · p. 5

2. Impossibility with n cops

The robber limits safe-zone growth and destroys cops as the cops explore. For a rooted start with all cops at one vertex, these constraints imply a lower bound of n + 1 cops on Cn.

2. Impossibility with n cops

  • The robber can limit safe-zone expansion to at most one new vertex per cops’ turn.When cops probe from both boundaries, the robber predicts their deterministic moves and occupies one target, eliminating the cop entering it.Source: §2 · p. 6
  • For a rooted start, whenever the safe zone has i + 1 vertices, the robber can eliminate at least i cops.The induction relies on cops needing to expand from both boundaries; the robber can occupy a target and eliminate an advancing cop during each expansion.Source: §2 · pp. 6–7
  • At least four cops must be alive when the safe zone expands from n − 2 to n − 1 vertices.With at most three alive, the robber can predict and occupy a proposed target, preventing the required expansion.Source: §2 · p. 7
  • n + 1 cops are necessary on Cn, even when all begin at one vertex.The proof combines the loss of at least n − 3 cops by the time the safe zone reaches n − 2 vertices with the need for at least four survivors to expand it to n − 1.Source: §2 · pp. 7–8

3. Cops and lethal robber

This section describes Capture-LR, which surrounds the robber on a ring from an arbitrary initial configuration by identifying safe-zone boundaries and expanding the safe zone until it spans the ring. It also explains how helpers are ordered by identifier to balance their movement across the safe zone before cops advance.

Capture-LR

  • Capture-LR surrounds the robber using at least max{ρ + ⌊log ρ⌋ + 4, n − ρ + 4} cops, where ρ is the initial unsafe-zone length.The guarantee applies from an arbitrary initial configuration.Source: §3 · p. 8

Step 1 (Determining the boundary)

  • In Step 1, cops probe unexplored directions to identify both safe-zone boundaries and gather surviving cops at them.Settlers and guards assign helpers as checkers; probe outcomes establish whether a direction is safe or leads toward the robber.Source: §3 · pp. 8, 10, 12

Step 2 (Expanding the safe zone)

  • Step 2 computes ˆρ as the largest x with x + ⌊log x⌋ + 2 ≤ N, then uses h = ⌊log ˆρ⌋ phases to expand the safe zone.Here N is the number of surviving cops gathered at the boundaries; all but the final phase have advancing, checking, and balancing sub-phases.Source: §3 · p. 14
  • Each phase pipelines helpers into the unsafe zone from both boundaries, checks the achieved extension, and balances helpers across the new boundaries.The lead guard probes successively farther until it finds an empty vertex or safely checks the full advance; a messenger reports its extension to the other guard.Source: §3 · pp. 15–16

Algorithm 7: Capture-LR: Step 2, Phase i - Sub-phase 3 (Balancing)

  • Balancing applies to a cop at step 2 and subphase 3.The algorithm labels this as Capture-LR, Step 2, Phase i, Sub-phase 3.Source: §3 · p. 18
  • Helpers order themselves by identifier; those with larger identifiers move through the safe zone toward the other guard while the remaining helpers wait di rounds.Source: §3 · p. 18
  • In the following round, every cop sets its phase to i + 1 and its subphase to 1.Source: §3 · p. 18

4. Correctness and complexity analysis

This section analyzes when Capture-LR’s two steps succeed in surrounding the robber and bounds its cop requirements, per-cop memory, and execution time for arbitrary initial ring configurations.

4. Correctness and complexity analysis

  • Step 1 loses at most two cops and requires a vertex with at least three cops or three vertices with at least two cops; n − ρ + 4 cops guarantee this condition.The proof shows that without this configuration, both boundary checkers could be eliminated, leaving no way to make further progress.Source: §4 · pp. 18–19
  • At Step 1’s completion, all living cops share ρ̄ and N and begin Step 2 simultaneously; if at least ρ + ⌊log ρ⌋ + 2 cops initiate Step 2, every cop computes the same ρ̂ ≥ ρ.Source: §4 · pp. 19–20
  • At most ρ̂ + 1 helpers ever advance toward the unsafe zone, while the h advancing sub-phases achieve total progress Sh ≥ ρ̂ − 1.Because cops can be eliminated from at most one side in a round, at least half of each phase’s advancers survive.Source: §4 · pp. 20, 21, 22, 25
  • A helper is available at the lead=1 guard for every checking sub-phase, and all living cops execute Step 2 synchronously, so the step does not stall.The available helper can act as the checker in each checking sub-phase.Source: §4 · pp. 22, 23, 25
  • With at least ρ + floor(log ρ) + 2 cops initiating Step 2, Capture-LR completes the step successfully and surrounds the robber.The proof accounts for the cops needed for advancing, checking, and guarding, and shows the safe zone eventually covers the ring.Source: §4 · p. 25
  • Capture-LR uses O(log n) bits of memory per cop and surrounds the robber within O(n^3) rounds.Each cop maintains only a constant number of parameters, each requiring O(log n) bits.Source: §4 · pp. 25–26

Correctness and complexity analysis

  • Capture-LR completes Step 1 in O(n^3) rounds and surrounds the robber in O(n^3) rounds overall.If ρ̂ ≥ 2n, Step 2 surrounds the robber within n rounds; otherwise, Step 2 takes O(n^2 log n) rounds.Source: §4 · pp. 26–27
  • For n ≥ 4, max{ρ + ⌊log ρ⌋ + 4, n − ρ + 4} cops suffice to surround the robber within O(n^3) rounds, with O(log n) bits per cop.Here, ρ is the unsafe-zone length in the initial configuration.Source: §4 · p. 27
  • The cop bound suffices for both steps: Step 1 needs k ≥ n − ρ + 4, while Step 2 needs at least ρ + ⌊log ρ⌋ + 2 surviving cops.At most two cops are eliminated during Step 1, so k ≥ ρ + ⌊log ρ⌋ + 4 ensures the Step 2 threshold.Source: §4 · p. 27
  • The rooted initial configuration is worst-case for Capture-LR and requires n + ⌊log n⌋ + 4 cops.Source: §4 · p. 27

5. Discussion and conclusion

The paper relates the lethal robber to a mobile lethal entity in Black Hole Search and interprets its strategy as progressively restricting the entity’s movement until capture becomes inevitable.

5. Discussion and conclusion

  • The lethal robber can be viewed as a mobile lethal entity, extending the black-hole analogy from a static dangerous vertex to a moving threat.The paper says the resulting algorithm can safely capture a mobile black-hole-like entity using mobile resources.Source: §5 · pp. 27–28
  • The algorithm progressively restricts the robber’s movement until capture becomes inevitable.Source: §5 · p. 28
  • The authors identify finding an algorithm using fewer cops and obtaining a better impossibility result as open directions.Source: §5 · p. 28
Loading 2609.06388v1…