The Computational Complexity of Pursuit Evasion

26 concepts17 papers2 proposals

Imagine trying to catch an invisible, highly agile intruder inside a sprawling, multi-story complex. If you have an infinite budget, you can simply station a guard at every single doorway and corridor, systematically narrowing down the intruder's hiding spots. But real-world resources are finite. What is the absolute minimum number of guards required to guarantee a catch, regardless of how cleverly the intruder flees?

This question lies at the heart of pursuit-evasion games—a family of mathematical models that includes Cops and Robbers, Hunters and Rabbit, and visibility-based search. While the premise is intuitively simple, determining this minimum team size (variously called the cop number, hunter number, or searcher number) or computing an optimal strategy is one of the most computationally stubborn challenges in computer science.

Why Pursuit-Evasion Explodes Combinatorially

To understand why pursuit-evasion is so difficult, consider the state space of a game played on a network (or graph). An exact algorithm cannot simply plan a single path; it must account for every possible location the evader could occupy at any given moment. Even if the evader is fully visible, the pursuers must anticipate every potential counter-move across an adversarial game tree.

Jan Kratochvíl et al. settled a long-standing open question in On tractability of Cops and Robbers game by proving that calculating the minimum number of cops needed to catch a robber is both NP-hard and W[2]-hard. This means that as the network grows, the problem becomes rapidly intractable, and we cannot even efficiently approximate the optimal number of pursuers within a logarithmic factor. As Connor Little and Christian Muise note in Domain Design for the Cops and Robbers Problem, this hardness arises directly from the combinatorial explosion of evaluating all possible initial positions and joint movement strategies.

The problem remains just as unforgiving when moving from abstract graphs to physical geometry. In visibility-based pursuit-evasion, pursuers sweep a continuous polygonal environment using line-of-sight sensors. Leonidas J. Guibas et al. demonstrated in A Visibility-Based Pursuit-Evasion Problem that finding the minimum number of pursuers in these geometric environments is NP-hard. When real-world constraints are added—such as sensors with a limited field of view—Brian P. Gerkey et al. showed in Visibility-Based Pursuit-Evasion with Limited Field of View that the problem remains firmly NP-hard, forcing roboticists to favor approximation and heuristics over exact optimality.

Information Asymmetry and the Invisible Target

The complexity escalates dramatically when the evader is invisible, introducing a severe information asymmetry. In the "Hunters and Rabbit" game, hunters must clear vertices of a graph without knowing where the rabbit is hiding.

Walid Ben-Ameur et al. proved in Hunting a rabbit is hard that computing the hunting number is NP-hard even on simple bipartite graphs. Crucially, the authors showed that restricting the game to a small, fixed number of rounds does not alleviate the hardness; short-term strategic planning is just as complex as long-term coordination. Furthermore, when games involve multi-step, multi-sensor configurations, Erik Halvorson et al. demonstrated in Multi-Step Multi-Sensor Hider-Seeker Games that finding an exact best response for either the seeker or the hider is NP-hard, illustrating that imperfect information creates a double-sided wall of intractability.

The Intuition of Recontamination

One of the most elegant structural insights into pursuit-evasion complexity involves recontamination—the idea that an evader can slip back into an area that the pursuers have already cleared.

If we force a strategy to be monotone (meaning cleared areas must be guarded so they remain cleared forever), the problem simplifies conceptually because it links directly to structural graph properties like pathwidth. However, forcing monotonicity can be highly inefficient. As Thomas Dissaux et al. discovered in Recontamination Helps a Lot to Hunt a Rabbit, allowing recontamination—letting the rabbit temporarily move back into previously cleared areas—can drastically reduce the number of hunters needed to win, even on basic structures like trees. Yet, as the authors later explored in Further results on the Hunters and Rabbit game through monotonicity, analyzing these non-monotone strategies is so mathematically elusive that their exact computational complexity remains an open problem for many graph classes.

Monotone Strategy:   [Cleared Zone] | [Guard] | [Unexplored Zone]  (No backtracking allowed)
Non-Monotone:        [Cleared Zone] <-> [Fluid Movement] <-> [Unexplored] (Fewer guards needed, but harder to plan)

Escalating to EXPTIME and PSPACE

When we alter the rules to allow faster evaders, partial observability, or infinite timelines, the complexity climbs even higher up the theoretical hierarchy:

Paths to Tractability

Faced with widespread intractability, researchers have carved out three main pathways to make these games solvable in practice.

1. Structural Parameterization

Instead of measuring complexity purely by the size of the graph or the number of agents, we can look at the underlying topology. Harmender Gahlawat and Meirav Zehavi demonstrated in Parameterized Analysis of the Cops and Robber Game and Parameterized Analysis of the Cops and Robber Problem that while the problem is W[2]-hard when parameterized by the number of cops, it becomes fixed-parameter tractable when parameterized by structural properties like the vertex cover number. They developed mathematical "kernels" to compress massive graphs into manageable sizes before running search algorithms.

2. Highly Structured Graph Families

Certain algebraic or geometric constraints naturally restrict the evader's options. For instance, Arindam Biswas and Jyoti Prakash Saha proved tight upper bounds on the cop number for highly symmetric algebraic structures, such as Cayley sum graphs, in On the cop number and the weak Meyniel conjecture for algebraic graphs, bypassing general-case hardness through algebraic symmetry.

3. Equilibrium Policy Generalization

Rather than computing exact combinatorial solutions for every new map, modern approaches leverage machine learning to approximate the game-theoretic structure. Runyu Lu et al. introduced a reinforcement learning framework in Equilibrium Policy Generalization: A Reinforcement Learning Framework for Cross-Graph Zero-Shot Generalization in Pursuit-Evasion Games that uses Nash equilibria to train neural network policies. These policies achieve zero-shot generalization across entirely unseen graphs, bypassing exponential runtime bottlenecks entirely by learning the underlying geometric intuition of the chase.

Key Foundational Work

Visibility-Based Pursuit-Evasion with Limited Field of View (2004) — contributed 2 concept elements to this direction.
A Visibility-Based Pursuit-Evasion Problem (1999) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_computational_complexity_of_pursuit_evas_8b2ab569,
  title = {computational complexity of pursuit-evasion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-pursuit-evasion/rdr_8b2ab5696d894158916721882cb67bf3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_complexity_of_pursuit_evas_8b2ab569_v1,
  title = {computational complexity of pursuit-evasion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-pursuit-evasion/rdr_8b2ab5696d894158916721882cb67bf3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake