Patrolling cop vs omniscient robber

This paper introduces and systematically analyzes a variant of the Cops and Robbers game where a cop follows a predetermined patrol against an omniscient robber, determining the minimum capture radius required for various graph classes including trees, grids, and chordal graphs.

The Gist

Here is an explanation of the paper "Patrolling Cop vs. Omniscient Robber," translated into everyday language with some creative analogies.

The Big Picture: A Game of "I Know Your Moves"

Imagine a classic game of Cops and Robbers played on a map (a graph). Usually, the Cop and the Robber take turns moving, and both can see exactly where the other is. The Cop wins by landing on the same spot as the Robber.

But this paper changes the rules to create a much harder scenario for the Cop:

1. The Robber is a Super-Computer (Omniscient): The Robber knows the Cop's entire plan before the game even starts. The Cop's route is fixed, printed on a piece of paper, and handed to the Robber.
2. The Cop is Blindfolded (Limited Vision): The Cop cannot see the Robber. The Cop just walks a pre-determined path (a "patrol") over and over again.
3. The Capture Radius: The Cop doesn't need to land on the exact same square to win. If the Cop gets within a certain distance (let's call it the "scream radius" or $\rho$), the Robber is caught.

The Question: How big does this "scream radius" need to be so that the Cop always catches the Robber, no matter how clever the Robber is?

---

The Main Characters and Concepts

1. The Patrol (The Cop's Routine)

Think of the Cop as a security guard walking a specific loop in a museum. The guard has a radio that can detect a thief within a certain range. The guard doesn't know where the thief is, but the thief knows exactly which room the guard will be in at 2:00 PM, 2:05 PM, and so on.

2. The "Triod" (The Three-Pronged Fork)

The researchers found that the hardest places for the Cop to catch the Robber are shapes that look like a three-way fork (a central point with three long paths sticking out).

• The Analogy: Imagine a T-junction in a hallway with three long wings. If the Robber is smart, they can run to the end of one wing, wait for the Cop to check that wing, and then dash to the end of a different wing before the Cop can turn around.
• The Result: The paper proves that if these "wings" are too long, the Cop needs a very large radius to catch the Robber. If the wings are short, a small radius is enough.

3. The "House" Strategy

In the math, they talk about "houses." Imagine the Robber hiding in a "safe house" at the end of a hallway.

• If the Cop's radius is too small, the Robber can hide in a house, wait for the Cop to pass by, and then run to a different house that the Cop hasn't checked yet.
• The paper calculates the exact length of the hallway where the Robber can successfully pull off this "switching houses" trick.

---

What They Found (The Results)

The authors tested this game on different types of maps (graphs) and found some interesting patterns:

1. Trees (Branching Paths)

• The Shape: Think of a tree with branches, but no loops.
• The Finding: The size of the Cop's radius depends entirely on the longest "three-way fork" in the tree.
• Simple Rule: If the longest fork has legs of length $L$, the Cop needs a radius of roughly $L/2$. If the radius is any smaller, the Robber can just run back and forth between the tips of the fork, always staying just out of reach.

2. Grids (City Blocks)

• The Shape: A checkerboard or a city grid.
• The Finding: This is tricky. The Cop can win by walking down the middle of the grid like a lawnmower.
• The Catch: If the grid is very wide, the Robber can hide on the far side. The paper gives a formula for the minimum radius needed based on how wide and tall the grid is. It turns out the Cop needs a radius of about half the width of the grid to be safe.

3. Chordal Graphs (Interval Graphs & Caterpillars)

• The Shape: These are complex shapes that look like a "caterpillar" (a central spine with little legs sticking out) or a stack of overlapping intervals (like a timeline).
• The Finding:
  • If the graph is a Caterpillar, the Cop wins with a radius of 0. This means the Cop just needs to walk the spine, and the Robber can't hide anywhere because the "legs" are too short to escape.
  • If the graph is a more complex Interval Graph (but not a caterpillar), the Cop needs a radius of 1. This means the Cop just needs to be able to "see" the Robber in the next room over to catch them.

---

Why Does This Matter?

You might ask, "Who cares about a game with a blindfolded cop?"

This isn't just a game; it models real-world security problems:

• Robot Patrols: Imagine a security robot that follows a fixed GPS route. It has a sensor with a limited range. How big does the sensor need to be to guarantee it catches an intruder who knows the robot's schedule?
• Network Security: Imagine a system administrator scanning a computer network on a fixed schedule to find a hacker who knows the scan times.
• The "Zero-Visibility" Problem: In many real-life scenarios, you can't see the enemy. You have to rely on a strategy that covers all possibilities without reacting to their moves. This paper helps us understand the "cost" of that blindness.

The Takeaway

The paper essentially says: "If you are the security guard with a fixed route and a limited sensor, your success depends entirely on the shape of the building."

• If the building has long, dead-end corridors (like a tree with long branches), you need a big sensor.
• If the building is a simple hallway (a caterpillar), a tiny sensor is enough.
• If the building is a city grid, you need a sensor that covers half the width of the city.

The "Omniscient Robber" represents the worst-case scenario: an enemy who knows your playbook. The paper tells us exactly how powerful our tools (the radius) need to be to beat that worst-case enemy.

Technical Summary

Here is a detailed technical summary of the paper "Patrolling cop vs omniscient robber" by Chiarelli et al.

1. Problem Definition

The paper investigates a variant of the classical Cops and Robbers game played on a finite, connected, undirected graph $G$. The game features two distinct deviations from the standard model:

• Predetermined Patrol (Offline Cop): The cop does not adapt their strategy based on the robber's moves. Instead, the cop follows a fixed walk (a "patrol") chosen before the game begins.
• Omniscient Robber: The robber possesses perfect information regarding the cop's entire patrol sequence in advance.
• Capture Radius ($\rho$): Capture occurs not only when the cop and robber occupy the same vertex, but when the robber is within a distance $\rho$ of the cop.

Objective: The authors define the parameter $\tilde{\rho}(G)$ as the minimum radius of capture required for the cop to guarantee a win against an optimal, omniscient robber on graph $G$. The goal is to determine the exact value or bounds of $\tilde{\rho}(G)$ for various graph classes.

2. Methodology and Tools

The authors employ a combination of combinatorial game theory, graph structural analysis, and topological mappings.

• Weak Retractions and Homomorphisms: A central tool is the concept of a weak homomorphism $\phi: V(G) \to V(H)$, where adjacent vertices in $G$ map to the same or adjacent vertices in $H$. If $H$ is a weak retract of $G$, the authors prove that if the robber can win on $H$ with radius $\rho$, they can also win on $G$ with the same radius. This allows the reduction of complex graphs to simpler subgraphs (like triods) to establish lower bounds.
• Strategic Simulation: For the robber's winning strategies, the authors construct "shadowing" strategies where the robber maintains a specific distance ($\rho+1$ or $\rho+2$) from the cop, effectively simulating the game on a simplified structure (like a tree or a cycle) embedded within the original graph.
• Depth-First Search (DFS) Patrols: For upper bounds (cop winning strategies), the authors often utilize DFS traversals or specific linear sweeps that ensure all vertices are "checked" (brought within range $\rho$) without allowing the robber to slip past undetected.
• Projection Maps: In the analysis of grids, the authors define complex projection maps ($\phi_\uparrow, \phi_\downarrow$) to map the grid graph onto a tree structure, allowing the robber to simulate a winning strategy on the tree within the grid.

3. Key Contributions and Results

A. Trees and Unicyclic Graphs

The paper provides exact values for $\tilde{\rho}(G)$ for trees and specific unicyclic graphs.

• Triods and $\ell_3$ Parameter: The authors define a triod as a tree with a central vertex of degree 3 and three branches. They define $\ell_3(T)$ as the distance from the origin to the closest leaf among the three branches.
• Main Theorem for Trees (Theorem 3.3): For any tree $T$, the minimum capture radius is:
  $$\tilde{\rho}(T) = \max_{v \in V(T)} \left\lfloor \frac{\ell_3(v)}{2} \right\rfloor$$
  This result implies that the cop's required radius is determined by the "worst-case" triod structure in the tree.
• Unicyclic Graphs ($T_{k,\ell}$): For graphs formed by a cycle of length $3k$with three paths of length$\ell$ attached at equidistant points, the value is:
  $$\tilde{\rho}(T_{k,\ell}) = \max \left\{ \left\lfloor \frac{\ell}{2} + \frac{k-2}{4} \right\rfloor, \left\lfloor \frac{3k-2}{2} \right\rfloor \right\}$$
• Clique-Triods: For a clique-triod (a clique with three attached paths), $\tilde{\rho}(G) = \lfloor \ell/2 \rfloor$, where $\ell$ is the path length.

B. Grid Graphs

The authors analyze the $n \times m$ grid graph $P_n \square P_m$.

• Bounds: They establish that:
  $$\min \left\{ \frac{n-3}{2}, \frac{2m+n-10}{8} \right\} \leq \tilde{\rho}(P_n \square P_m) \leq \frac{n}{2}$$
• Technique: The lower bound is proven by constructing a robber strategy that utilizes a "switching area" to move between branches of an embedded tree structure, effectively escaping the cop's fixed patrol.

C. Chordal Graphs

The study extends to chordal graphs, specifically caterpillars and interval graphs.

• Caterpillars: The authors prove that $\tilde{\rho}(G) = 0$ if and only if $G$ is a caterpillar. This means a cop with a fixed patrol can catch a robber on a caterpillar even with zero capture radius (i.e., they must occupy the same vertex), provided the cop follows a specific backbone traversal.
• Interval Graphs:
  • If $G$ is a caterpillar, $\tilde{\rho}(G) = 0$.
  • If $G$ is a connected interval graph but not a caterpillar, $\tilde{\rho}(G) = 1$.
  • This implies that for non-caterpillar interval graphs, a capture radius of 1 is sufficient and necessary.
• Conjecture for General Chordal Graphs: The authors conjecture that for any connected chordal graph $G$ and $\rho \geq 2$, $\tilde{\rho}(G) \geq \rho$ if and only if $G$ contains a weak retract that is either a triod with $\ell_3(T) \geq 2\rho$ or a clique-triod with $\ell_3(G) \geq 2\rho - 1$.

4. Significance and Impact

• Bridging Visibility and Determinism: The paper uniquely bridges the gap between limited-visibility games (where cops cannot see the robber) and offline pursuit-evasion (predetermined paths). It demonstrates that even with perfect information about the cop's path, an omniscient robber can evade capture unless the cop has a sufficient "sensing radius."
• Structural Characterization: The work provides a structural characterization of graphs based on their "triod" complexity. It identifies that the difficulty of patrolling a graph is intrinsically linked to the presence of specific branching structures (triods) and their sizes.
• Generalization of Watchman's Walk: The problem generalizes the "Watchman's Walk" problem. While a watchman's walk requires visiting every vertex, this model requires "seeing" every vertex within a radius $\rho$, offering a more flexible metric for security and surveillance applications.
• New Game Theoretic Tools: The development of the weak retraction technique for lower bounds and the projection-based strategies for grids offers new methodological tools for analyzing pursuit-evasion games with restricted information.

In summary, the paper establishes a rigorous framework for analyzing deterministic patrolling against omniscient adversaries, providing exact solutions for trees and interval graphs, and offering tight bounds and conjectures for grids and general chordal graphs.