# Cops and Robbers on Multi-Layer Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Mar 2023.

## Built on by (most cited first, 1 of 1)

- [Domain Design for the Cops and Robbers Problem](https://mlsanity.com/paper/2607.18274/) (2026)

## Abstract (arXiv)

We generalise the popular cops and robbers game to multi-layer graphs, where each cop and the robber are restricted to a single layer (or set of edges). We show that initial intuition about the best way to allocate cops to layers is not always correct, and prove that the multi-layer cop number is neither bounded from above nor below by any increasing function of the cop numbers of the individual layers. We determine that it is NP-hard to decide if k cops are sufficient to catch the robber, even if every cop layer is a tree and a set of isolated vertices. However, we give a polynomial time algorithm to determine if k cops can win when the robber layer is a tree. Additionally, we investigate a question of worst-case divisions of a simple graph into layers: given a simple graph G, what is the maximum number of cops required to catch a robber over all multi-layer graphs where each edge of G is in at least one layer and all layers are connected? For cliques, suitably dense random graphs, and graphs of bounded treewidth, we determine this parameter up to multiplicative constants. Lastly we consider a multi-layer variant of Meyniel's conjecture, and show the existence of an infinite family of graphs whose multi-layer cop number is bounded from below by a constant times n / log n, where n is the number of vertices in the graph.