# Domain Design for the Cops and Robbers Problem

arXiv: https://arxiv.org/abs/2607.18274 · HTML: https://mlsanity.com/paper/2607.18274/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 22 references that are in the map.
- First posted on arXiv 15 Jun 2026.

## Builds on (most cited first, 1 of 1)

- [Cops and Robbers on Multi-Layer Graphs](https://mlsanity.com/paper/2303.03962/) (2023)

## Abstract (arXiv)

Cops and Robbers is a well-studied problem in graph theory. The setting consists of a robber and one or more cops placed on an undirected graph. Taking turns moving throughout the graph, the cops try to capture the robber. The property of interest is whether k cops suffice to ensure at least one cop occupies the same vertex as the robber, after a finite number of turns, given any configuration of their initial placement; if successful, the graph is referred to as ``k-copwin''. In this work, we cast the problem of determining whether a graph is k-copwin as a non-deterministic planning problem and use state-of-the-art planners to compute this property. The cop movement is cast as non-deterministic movement (to capture all possible strategies), while the robber movement is deterministic in nature. We also extend the base model using several variations from the graph theory literature.