Computing strategies for multiple cops on infinite graphs

Abstract

Cops and robbers is a vertex pursuit game played on connected reflexive graphs. While the game is most often played with a single cop on a finite graph, we consider the variation in which n cops pursue the robber on an infinite graph. For each $n ⩾ 2$ , we show there is a computable graph which is classically cop-win and can be won by n cops using a computable strategy, but cannot be won by $n - 1$ cops using a computable strategy. Furthermore, we show that the index set of n-cop-win computable graphs is $Π_{1}^{1}$ -complete.

Keywords

Computability theory game of cops and robbers

1. Introduction

The game of cops and robbers was introduced independently in Quilliot [8] and in Nowakowski and Winkler [7]. The original game is played on a graph G by two players: the cop and the robber. The game begins with the cop, followed by the robber, choosing a vertex on which to start. In subsequent rounds, the players take turns (with the cop going first) moving from their current vertex to one of the neighboring vertices. The game ends, and the cop wins, if she shares a vertex with the robber at any point in the play. The robber wins if he manages to avoid ever sharing a vertex with the cop.

There are two standard assumptions made on the graphs used in this game. First, the robber can always win when the game is played on a disconnected graph by choosing a starting node in a different component from the cop’s starting position. To avoid this triviality, we assume our graphs are connected. Second, to allow the players to choose to remain on their current vertex in any given round, we assume the edge relation is reflexive. We make the additional assumption here that our graphs are at most countable because our eventual concern is with computable graphs and strategies.

Cops and robbers is an open game, and therefore, for any fixed graph G, one of the players has a winning strategy when the game is played on G. G is called cop-win when the cop has a winning strategy and robber-win otherwise (when the robber has a winning strategy). Nowakowski and Winkler [7] gave two structural characterizations of cop-win graphs. The first characterization applies to finite graphs and shows there is a polynomial time algorithm to determine if a finite graph is cop-win. The second characterization applies to all graphs and was used by Stahl [10] to show the index set of computable cop-win graphs is $Π_{1}^{1}$ -complete.

From the perspective of computability theory, we would like to understand the complexity of strategies required to win this game on computable graphs. It is not difficult to use trees to code information into robber-win strategies. For each computable ordinal α, Stahl [10] gave an example of a computable graph that is robber-win and such that every robber-win strategy computes $0^{(α)}$ . It is more challenging to deal with cop-win strategies. Nonetheless, Stahl [10] constructed a computable graph that is classically cop-win but not by a computable cop strategy.

In this paper, we extend these results to a variation of cops and robbers in which there are multiple cops. The version with n cops is played in rounds as before. In the initial round, the player controlling the cops chooses a starting vertex for each cop, after which the player controlling the robber chooses a starting vertex for the robber. In the subsequent rounds, each cop moves to a neighboring vertex, followed by the robber moving to a neighboring vertex. The cops win if any cop shares a vertex with the robber at any point in the play, and otherwise, the robber wins.

The game with n cops is still an open game, so for any n and G, there is either a winning strategy for the n cops (and G is n-cop-win) or there is a winning strategy for the robber (and G is robber-win or not n-cop-win to emphasize the number of cops in the game). Note that if $n = | G |$ , then G is n-cop-win because the player for the cops can place one cop on each vertex in the initial round.

The minimum number of cops required to win on a fixed graph G is called the cop-number of G, denoted $c (G)$ . This notion is well studied for finite graphs and there are many results in the literature giving upper and lower bounds for various classes of graphs. For example, $c (G) ⩽ 3$ for finite planar graph G (by Aigner and Fromme [1]), while $c (G) ⩽ 2$ for finite outerplanar graphs (by Clarke [5]).

In Section 2, we consider the complexity of strategies in the game with n cops on computable graphs. We show that Stahl’s examples for coding information into robber strategies continue to work in this context. More interestingly, for each $n ⩾ 2$ , we construct a computable graph G such that G is cop-win classically, G can be won by n cops following a computable strategy, but G cannot be won by $n - 1$ cops following a computable strategy. Thus we can achieve any desired “computable cop-number” with a graph which is classically cop-win.

In Section 3, we show that for each $n ⩾ 2$ , the index set of computable graphs that are n-cop-win is $Π_{1}^{1}$ -complete. The hardness half of this result comes directly from Stahl [10], but to show that the index set is $Π_{1}^{1}$ , we use a structural characterization of n-cop-win graphs by Clarke and MacGillivray [6].

Our notation for computability theory is standard and follows Soare [9] and Ash and Knight [2]. Bonato and Nowakowski [4] and Bonato [3] are excellent introductions to cops and robbers and to vertex pursuit games (and other games on graphs) more generally.

2. Computable strategies

We consider the game of cops and robbers with n cops on a reflexive connected graph G with vertices ${v_{n} ∣ n \in ω}$ . For determining whether G is n-cop-win or robber-win, there is no loss of generality in requiring all the cops to start the game at $v_{0}$ . That is, suppose the cops are initially placed at $v_{0}$ , but a cop-winning strategy wants the cops to start elsewhere. Since G is connected, each cop can move along a path from $v_{0}$ to their desired starting vertex in the opening rounds of the game. Once all of the cops have reached their locations, they can follow the cop-winning strategy.

To formalize the definition of a strategy, we denote the position of the robber in round i by $r_{i} \in ω$ (indicating that the robber is on $v_{r_{i}}$ ) and the positions of the n cops by a string $γ_{i} \in ω^{n}$ (indicating that the k-th cop is on $v_{γ_{i} (k)}$ ). Since we assume the cops start at $v_{0}$ , we have $γ_{0} = 0^{n}$ .

The history of the game at any point can be represented by a tuple of the form $⟨ γ_{0}, r_{0}, γ_{1}, r_{1}, \dots, γ_{j} ⟩$ or $⟨ γ_{0}, r_{0}, γ_{1}, r_{1}, \dots, γ_{j}, r_{j} ⟩$ , depending on whether the cops or the robber moved last. The sequence represents a legal play as long as $γ_{0} = 0^{n}$ and there are edges between $v_{r_{i}}$ and $v_{r_{i + 1}}$ and between $γ_{i} (k)$ and $γ_{i + 1} (k)$ for each $k < n$ . The sequence represents a cop win if there is an i and $k < n$ such that $r_{i} = γ_{i} (k)$ or $r_{i} = γ_{i + 1} (k)$ .

Coding sequences by numbers, the states of the game become elements of ω. An n-cop strategy on a graph G is a function $f : ω \to ω$ that takes (a code for) a state of the game as input and outputs an allowable cop move. More formally, if m represents a legal state of the game $⟨ γ_{0}, r_{0}, \dots, γ_{j}, r_{j} ⟩$ , then $f (m)$ is (the code for) an n-tuple τ such that $⟨ γ_{0}, r_{0}, \dots, γ_{j}, r_{j}, τ ⟩$ is a legal move.

We say that a (finite or infinite) play of the game $γ_{0}, r_{0}, γ_{1}, r_{1}, \dots$ follows the n-cop strategy f if $γ_{0} = 0^{n}$ and $γ_{i + 1} = f (⟨ γ_{0}, r_{0} \dots, γ_{i}, r_{i} ⟩)$ for each i. An n-cop strategy f is winning if the cops win every legal play that follows f.

Analogously, a robber strategy on G is a function $f : ω \to ω$ that outputs an allowable robber move when it is the robber’s turn. The play $γ_{0}, r_{0}, γ_{1}, r_{1}, \dots$ follows the robber strategy f if $r_{i} = f (⟨ γ_{0}, r_{0} \dots, γ_{i} ⟩)$ for each i. A robber strategy f is winning if the robber wins every legal play that follows f.

Note that the set of strings representing legal plays on a computable graph G is computable. A computable n-cop strategy for G is a total computable function f that is an n-cop strategy for G.

We use known results to code information into robber strategies. We can view a tree $T \subseteq ω^{< ω}$ as a graph by letting the elements of T be the nodes in the graph and putting an edge between each node and its immediate successors on T (e.g. between σ and $σ^{⌢} n$ , if both are on T). Without loss of generality, we assume $v_{0}$ is the root of the tree. If T has an infinite path, then the corresponding graph is robber-win because the robber can move along the infinite path ahead of the cop. Otherwise, T is cop-win because the cop can chase the robber to a leaf. Building on this intuition, Stahl [10] proved that any robber-win strategy on T computes an infinite path. Her argument to code hyperarithmetic sets into robber-win strategies carries over immediately to games with n-cops.

Lemma 2.1 Stahl [10]

Let $T \subseteq ω^{< ω}$ be a tree with an infinite path. Every robber-win strategy computes an infinite path in T.

Theorem 2.2.
For each computable ordinal α and $n ⩾ 1$ , there is a robber-win graph in the game with n cops such that every robber-win strategy computes $0^{(α)}$ .
Proof.
Let T be a computable tree with infinite paths such that every path computes $0^{(α)}$ . We assume without loss of generality that all the cops start at the root node. Because the graph is a tree, there is a unique shortest path between the cops and the robber and the distance-minimizing strategy of moving directly towards the robber is the optimal cop strategy. It follows that there is no advantage from having n cops and hence Lemma 2.1 (or more precisely, its proof) applies in this context as well.

Turning to cop strategies, for each $n ⩾ 2$ , we show there is a computable graph that can be won computably by n cops but not by $n - 1$ cops, with no limitations on the complexity of the robber strategy. Furthermore, we realize this behavior on graphs that are classically cop-win by a single cop.
Theorem 2.3.
For each $n ⩾ 2$ , there is a computable graph $G_{n}$ that is cop-win, has a computable n-cop winning strategy, but does not have a computable $(n - 1)$ -cop winning strategy.
Proof.
Fix $n ⩾ 2$ . We suppress the subscript n, writing G in place of $G_{n}$ . Initially, G consists of a root node $v_{0}$ (where the cops start) attached to infinitely many nodes $x^{e}$ extended by a second node $a_{0}^{e}$ as shown in Fig. 1.

To diagonalize against the partial computable function $Φ_{e}$ being an $(n - 1)$ -cop winning strategy, we build a subgraph called the e-section starting with the nodes $x^{e}$ and $a_{0}^{e}$ . The e-sections are disjoint and only accessible through $x^{e}$ , so we construct them independently. We assume the reflexive edges are added automatically and will not explicitly mention them or show them in diagrams.

To decide how to expand the e-section, we simulate a play of the game with $n - 1$ cops, allowing $Φ_{e}$ to control cops. In the simulated game, the robber starts at $a_{0}^{e}$ . We do not add points to the e-section unless $Φ_{e}$ moves a cop into a position adjacent to the robber. At that stage, we expand the e-section to give the robber an escape route in a controlled way so that G remains cop-win and so that n computable cops can win on G. For ease of notation, we fix e and drop the superscripts.

Consider $Φ_{e}$ on the initial cop position $0^{n - 1}$ (i.e. all start at $v_{0}$ ) and the initial robber position $a_{0}$ . At each stage s, we check if $Φ_{e, s} (⟨ 0^{n - 1}, a_{0} ⟩)$ converges. If not, then we pass to the next stage and check this computation again. If $Φ_{e, s} (⟨ 0^{n - 1}, a_{0} ⟩) ↓= γ_{1}$ , then we need to determine if one of the cops has moved into a position to threaten the robber. If x is not among the nodes in $γ_{1}$ , then we leave the robber at $a_{0}$ and shift to checking whether $Φ_{e, s} (⟨ 0^{n - 1}, a_{0}, γ_{1}, a_{0} ⟩)$ converges at future stages. We continue this process each time $Φ_{e}$ converges until we see an output that places a cop at x (assuming $Φ_{e}$ outputs legal moves). Notice that no cop can reach $a_{0}$ without first passing through x.

More formally, suppose we have completed the j-th round without the cop positions $γ_{1}, \dots, γ_{j}$ containing the node x. If we see $Φ_{e, s} (⟨ 0^{n - 1}, a_{1}, \dots, γ_{j}, a_{1} ⟩) ↓= γ_{j + 1}$ but x is not one of the cop positions in $γ_{j + 1}$ , then we check $Φ_{e} (⟨ 0^{n - 1}, a_{0}, \dots, γ_{j + 1}, a_{0} ⟩)$ at future stages. We refer to this process as “watching $Φ_{e}$ while keeping the robber at $a_{0}$ until a cop is moved adjacent to $a_{0}$ .”

If $Φ_{e}$ outputs a non-legal move, then $Φ_{e}$ has lost already and we can stop building the e-section. Therefore, without loss of generality, we assume whenever $Φ_{e}$ outputs a tuple $γ_{j + 1}$ representing the cop positions, each node $γ_{j + 1} (k)$ has already been placed in G with an edge to the node $γ_{j} (k)$ .

If $Φ_{e}$ eventually moves a cop to x, then we add vertices $a_{1}$ and $y_{i}^{0}$ , for $i < n$ , to the e-section with edges from $a_{1}$ to $a_{0}$ and from each $y_{i}^{0}$ to $a_{0}$ , $a_{1}$ and x. For readability, we show the connections just from $y_{0}^{0}$ in Fig. 2. (Note that the $y_{i}^{0}$ nodes are not connected to each other.)

No cop in the simulated game is currently at a neighbor of $a_{1}$ , because we just added the $y_{i}^{0}$ nodes and because no cop can be at $a_{0}$ since the first cop only just arrived at x. Therefore, in our simulated game, we can move the robber to $a_{1}$ knowing that each cop is at least two nodes away from $a_{1}$ .

We now enter the main loop of the construction of the e-section. We continue the process described above to compute the movement of the cops under $Φ_{e}$ , keeping the robber at $a_{1}$ unless a cop moves to a node adjacent to $a_{1}$ . If $Φ_{e}$ never moves a cop adjacent to $a_{1}$ , then the robber wins and $Φ_{e}$ is not a winning strategy.

Suppose $Φ_{e}$ moves a cop to $a_{0}$ or some $y_{i}^{0}$ . Since $Φ_{e}$ only controls $n - 1$ cops, at least one node $y_{j}^{0}$ does not contain a cop. Let $z_{0}$ denote such a node. We expand the e-section by adding vertices $a_{2}$ and $y_{i}^{1}$ for $i < n$ . We add edges from $a_{2}$ to $a_{1}$ and $z_{0}$ , and from each $y_{i}^{1}$ to $a_{1}$ , $a_{2}$ , $z_{0}$ and x. For readability, we only show the edges from $y_{0}^{1}$ in Fig. 3 and we don’t show the $y_{i}^{0}$ nodes other than $z_{0}$ .

We repeat this process. No cop is currently adjacent to $a_{2}$ in the simulated game, so we move the robber to $a_{2}$ and continue to compute the trajectory of the cops using $Φ_{e}$ , keeping the robber at $a_{2}$ unless a cop moves to an adjacent node.

If a cop moves to $z_{0}$ , $a_{1}$ , or some $y_{i}^{1}$ , we expand the e-section by adding vertices $a_{3}$ and $y_{i}^{2}$ for $i < n$ . There is at least one $y_{j}^{1}$ that does not contain a cop and we let $z_{1}$ denote such a node. We add edges from $a_{3}$ to $a_{2}$ and $z_{1}$ , and from each $y_{i}^{2}$ to $a_{2}$ , $a_{3}$ , $z_{1}$ and x. In Fig. 4, we only show edges from $y_{0}^{2}$ and we don’t show the $y_{i}^{0}$ or $y_{i}^{1}$ nodes other than $z_{0}$ and $z_{1}$ .

In general, for $k ⩾ 1$ , when $a_{k + 1}$ is added, it is connected to $a_{k}$ , $z_{k - 1}$ and each $y_{i}^{k}$ with $i < n$ . We simulate the game using $Φ_{e}$ with the robber at $a_{k + 1}$ . If $Φ_{e}$ moves a cop to one of these neighbors of $a_{k + 1}$ , the graph is expanded by adding $a_{k + 2}$ and $y_{i}^{k + 1}$ for $i < n$ . We set $z_{k}$ to be a node of the form $y_{j}^{k}$ that does contain have a cop. We add edges from $a_{k + 2}$ to $a_{k + 1}$ and $z_{k}$ , and from each $y_{i}^{k + 1}$ to $a_{k + 2}$ , $a_{k + 1}$ , $z_{k}$ and x. We move the robber to $a_{k + 2}$ and continue the simulated game.

This completes the description of the construction. Note that the e-section could be finite or infinite. The nodes $z_{k}$ are connected to x, $a_{k}$ , $a_{k + 1}$ , $a_{k + 2}$ , $y_{i}^{k + 1}$ for $i < n$ , and $z_{k - 1}$ (except for $z_{0}$ as there is no node $z_{- 1}$ ). The other nodes of the form $y_{i}^{k}$ are connected to x, $a_{k}$ , $a_{k + 1}$ and $z_{k - 1}$ (except for the $y_{i}^{0}$ nodes as there is no node $z_{- 1}$ ).

In each e-section, we refer to the set of $a_{j}$ points as the vertical segment and the set of points $y_{i}^{j}$ and $z_{i}$ as the horizontal section. Importantly, x is connected to every point in the horizontal section.

It remains to check the properties of G stated in the theorem. It is immediate that if $Φ_{e}$ is a computable $(n - 1)$ -cop strategy, then the robber can beat $Φ_{e}$ by starting at the node $a_{0}^{e}$ and moving up the vertical segment of the e-section each time a new node $a_{k + 1}^{e}$ appears (i.e. when $Φ_{e}$ moves a cop adjacent to the robber).
Lemma 2.4.
The graph G can be won with n cops following a computable strategy.
Proof.
The cops start at $v_{0}$ , so we can assume the robber does not. Fix e such that the robber starts in the e-section. In the first round, all the cops move to $x^{e}$ . The remainder of the game will stay in the e-section, so we drop the superscripts. If the robber’s next move is to the horizontal segment or to $a_{0}$ , then a cop can move directly there and win. Therefore, assume the robber moves to $a_{k}$ with $k ⩾ 1$ .

Since $a_{k}$ is in G, the nodes $y_{i}^{k - 1}$ for $i < n$ are also already in G. The cops move to place one cop on each $y_{i}^{k - 1}$ . The analysis splits into cases depending on whether $k ⩾ 2$ or $k = 1$ .

Suppose $k ⩾ 2$ . The nodes connected to $a_{k}$ (if they exist in G) are $a_{k - 1}$ , $a_{k}$ , $a_{k + 1}$ , $z_{k - 2}$ , and $y_{i}^{k - 1}$ and $y_{i}^{k}$ for $i < n$ . There is a cop on each $y_{i}^{k - 1}$ , so we assume the robber does not move to one of these nodes. The cop positions include $z_{k - 1}$ , although exactly which node is $z_{k - 1}$ might not have been specified yet. The nodes connected to $z_{k - 1}$ (if they exist in G) are x, $a_{k - 1}$ , $a_{k}$ , $a_{k + 1}$ , $z_{k - 2}$ , and $y_{i}^{k}$ for $i < n$ . Therefore, $z_{k - 1}$ covers the remaining nodes that the robber could move to.

Suppose $k = 1$ . The nodes connected to $a_{1}$ (if they exist in G) are $a_{0}$ , $a_{1}$ , $a_{2}$ , and $y_{i}^{0}$ and $y_{k}^{1}$ for $i < n$ (i.e. the same nodes as in the $k ⩾ 2$ case except there is no $z_{- 1}$ node). There is a cop on each $y_{i}^{0}$ nodes, so we assume the robber does not move to one of these nodes. The cop positions include $z_{0}$ , which is connected to x, $a_{0}$ , $a_{1}$ , $a_{2}$ , and $y_{i}^{1}$ for $i < n$ (if they exist in G). Therefore, $z_{0}$ covers the remaining nodes the robber could move to.
Lemma 2.5.
The graph G can be won by 1 cop following a classical strategy.
Proof.
The cop starts at $v_{0}$ . We assume the robber starts in the e-section of the graph and the cop moves to $x^{e}$ . As above, we assume the robber moves to $a_{k}$ with $k ⩾ 1$ . The key difference in this lemma is that the classical cop knows the entire graph at the end of the construction rather than having to respond at a finite stage when the graph is not yet complete. The proof breaks into four cases.

Suppose the robber is at $a_{1}$ and there is no node $a_{2}$ in G. The cop moves to $a_{0}$ . The nodes connected to $a_{1}$ are $a_{0}$ , $a_{1}$ and $y_{i}^{0}$ for $i < n$ (see Fig. 2). All of these nodes are also connected to $a_{0}$ , so the cop wins on her next move.

Suppose the robber is at $a_{1}$ and the node $a_{2}$ exists. In this case, the nodes $y_{i}^{1}$ exist and the node $z_{0}$ is specified. The cop moves to $z_{0}$ . The only nodes connected to $a_{1}$ that are not connected to $z_{0}$ are the $y_{i}^{0}$ nodes other than $z_{0}$ (see Figs. 2 and 3). Therefore, assume the robber moves to such a node $y_{i}^{0}$ . Since $y_{i}^{0} \neq z_{0}$ , this node is only connected to x, $a_{0}$ , $a_{1}$ and itself. All of these nodes are connected to $a_{0}$ , so the cop can move to $a_{0}$ and guarantee a win on her next turn.

Suppose the robber is at $a_{k}$ for $k ⩾ 2$ and there is no node $a_{k + 1}$ in G. The cop moves to $y_{0}^{k - 1}$ . The only viable option for the robber is to move to $y_{i}^{k - 1}$ for some $0 < i < n$ . Then the cop moves to $z_{k - 2}$ which covers all the nodes connected to $y_{i}^{k - 1}$ .

Suppose the robber is at $a_{k}$ with $k ⩾ 2$ and $a_{k + 1}$ exists in G. The cop moves to $z_{k - 1}$ . As above, the only nodes connected to $a_{k}$ that are not connected to $z_{k - 1}$ are the $y_{i}^{k - 1}$ nodes other than $z_{k - 1}$ . However, if the robber moves to $y_{i}^{k - 1}$ , the cop can move to $z_{k - 2}$ . The only nodes connected to $y_{i}^{k - 1}$ (which, recall, is not $z_{k - 1}$ ) are x, $z_{k - 2}$ , $a_{k}$ , $a_{k + 1}$ and itself. However, each of these nodes is connected to $z_{k - 2}$ , so the cop can win on her next turn.

This completes the proof of Theorem 2.3.

Figure 1.
Initial set-up for G.

Figure 2.
Nodes added when a cop moves adjacent to $a_{1}$ .

Figure 3.
Nodes added when a cop moves adjacent to $a_{2}$ .

Figure 4.
Nodes added when a cop moves adjacent to $a_{3}$ .
3. Index sets

In this section, we show that for each $n ⩾ 2$ , the index set of computable n-cop-win graphs is $Π_{1}^{1}$ -complete. The proof resembles the proof in Stahl [10] that the index set of computable cop-win graphs is $Π_{1}^{1}$ complete. The main difference is that we use a characterization of n-cop-win graphs by Clarke and MacGillivray [6]. Clarke and MacGillivray prove the characterization for finite graphs, although they note it can be modified for infinite graphs. For completeness, we make these modifications and give a proof that works for all graphs.

Let G be a graph with vertex set V and edge relation E. For $v \in V$ , we let $N_{G} [v] = {x \in V : E v x ~holds}$ denote the set of neighbors of v. The n-th categorical product $G^{n}$ of G is the graph with vertex set $V^{n}$ and an edge between $p, q \in V^{n}$ if and only if for all $i < n$ , $E p (i) q (i)$ holds. If G is connected and reflexive, then so is the product graph $G^{n}$ . Fixing notation, throughout this section, we use v, x and y to range over V and p and q to range over $V^{n}$ .

To keep track of the cop positions in the n-cop game, we imagine a single player moving on $G^{n}$ rather than n different cops moving on G. We define a family of relations $⩽_{α}$ on $V \times V^{n}$ indexed by ordinals. The intuition for $v ⩽_{α} p$ is that the cops can win in α turns when the robber is on v, the cops are on $p (0), \dots, p (n - 1)$ and it is the robber’s turn to move.

Formally, the relations $⩽_{α}$ are defined by transfinite recursion. For $v \in V$ and $p \in V^{n}$ , $v ⩽_{0} p$ if and only if $v = p (i)$ for some $i < n$ . That is, $v ⩽_{0} p$ indicates that the cops have captured the robber. For $α > 0$ , $v ⩽_{α} p$ if and only if

\begin{aligned} (\forall y \in N_{G} [v]) (\exists q \in N_{G^{n}} [p]) (\exists β < α) (y ⩽_{β} q) \end{aligned}

(1)

In other words, no matter where the robber moves on his next turn, the cops can improve their positions relative to the robber when they move.

It follows immediately from this definition that $γ ⩽ α$ implies $⩽_{γ} \subseteq ⩽_{α}$ . Therefore, there is an ordinal δ at which this sequence stabilizes (i.e. at which $⩽_{α} = ⩽_{δ}$ for all $α ⩾ δ$ ). We let $⪯_{G}$ denote this limiting relation $⩽_{δ}$ . We prove Clarke and MacGillivray’s theorem with no restrictions on the size of the graph.

Theorem 3.1 Clarke and MacGillivray [6]

G is n-cop-win if and only if the relation $⪯_{G}$ is trivial (i.e. $v ⪯_{G} p$ for all $v \in V$ and $p \in V^{n}$ ).

Proof.

Suppose $⪯_{G}$ is trivial. Let $p_{0} = ⟨ v_{0}, \dots, v_{0} ⟩$ be the cops’ fixed starting position, let $x_{0}$ be the robber’s starting position, and assume $p_{1} = p_{0}$ (i.e. the cops don’t move on their first turn). Since $⪯_{G}$ is trivial, we can fix an ordinal $α_{0}$ such that $x_{0} ⩽_{α_{0}} p_{1}$ . In general, let $x_{k}$ denote the position of the robber in round k, $p_{k + 1}$ denote the positions of the cops in round $k + 1$ , and $α_{k}$ be the least ordinal such that $x_{k} ⩽_{α_{k}} p_{k + 1}$ . By condition (1), for any robber move $x_{k + 1}$ , the cops can choose $p_{k + 2}$ so that $x_{k + 1} ⩽_{α_{k + 1}} p_{k + 2}$ with $α_{k + 1} < α_{k}$ . Therefore, in finitely many rounds, we arrive at $x_{ℓ} ⩽_{0} p_{ℓ + 1}$ and the cops win.

Conversely, suppose that $⪯_{G}$ is not trivial. Fix α such that $⪯_{G} = ⩽_{α} = ⩽_{α + 1}$ . Consider any $x \in V$ and $p \in V^{n}$ such that $x ⋠_{G} p$ . Since $x ⋠_{α + 1} p$ , condition (1) fails, and so there is a node y adjacent to x such that $y ≰_{α} q$ (and hence $y ⋠_{G} q$ ) for all cop positions q adjacent to p. It follows that if the players are at positions such that $x ⋠ p$ , then the robber can move to maintain this condition and thus avoid capture forever. In particular, the robber has a strategy to win if the cops start at the positions specified by p. However, since the starting position for the cops doesn’t affect whether G is n-cop win or not, we conclude that G is robber-win in the game with n cops.

For a total computable function $Φ_{e}$ , we define the computable graph $G_{e}$ to have vertex set ω with $Φ_{e}$ giving the characteristic function of the edge relation: if $Φ_{e} (x, y) = 1$ , then there an edge between x and y, and if $Φ_{e} (x, y) = 0$ , then there is no edge. It is arithmetical (even $Π_{2}^{0}$ ) to say $Φ_{e}$ is total and the resulting computable graph $G_{e}$ is reflexive and connected. We form the computable product graph $G_{e}^{n}$ in the obvious way by considering computations on n-tuples.

Theorem 3.2.

For each $n ⩾ 2$ , the index set $I_{n} = {e : G_{e} ~is a~ n - cop-win graph}$ is $Π_{1}^{1}$ -complete.

Proof.

We have already noted that a tree $T \subseteq ω^{< ω}$ is n-cop-win if and only if T has no infinite path. Since the relation of a computable tree having no infinite path is $Π_{1}^{1}$ -hard, it follows that $I_{n}$ is $Π_{1}^{1}$ -hard. Therefore, it suffices to show that $I_{n}$ has a $Π_{1}^{1}$ definition.

Our $Π_{1}^{1}$ definition will say that $e \in I_{n}$ if and only if $G_{e}$ is a computable reflexive connected graph and every relation that “looks like” $⪯_{G_{e}}$ is trivial. The first condition is arithmetical, so we focus on the second condition.

Suppose $G_{e}$ is a computable reflexive connected graph. The relation $⪯_{G_{e}}$ has two fundamental properties. First, since $⩽_{0} \subseteq ⪯_{G_{e}}$ , we have $x ⪯_{G_{e}} p$ whenever $x = p (i)$ for some $i < n$ . Second, by condition (1), if $(\forall y \in N_{G} [x]) (\exists q \in N_{G^{n}} [p]) (y ⪯_{G_{e}} q)$ , then $x ⪯_{G_{e}} p$ .

We capture these properties by arithmetic formulas with a free variable R ranging over $(n + 1)$ -arity relations. In these formulas, let x and y be single variables and let p and q be n-tuples of variables $p_{0}, \dots, p_{n - 1}$ and $q_{0}, \dots, q_{n - 1}$ (i.e. x, y range over the vertices in $G_{e}$ and p, q range over the vertices in $G_{e}^{n}$ ). Let $ψ_{1} (R)$ capture the first property

(\forall x, p) ((x = p_{0} \lor \dots \lor x = p_{n - 1}) \to R (x, p))

and let

ψ_{2} (R)

capture the second property

(\forall x, p) [(\forall y \in N_{G} [x]) (\exists q \in N_{G_{e}^{n}} [p]) (R (y, q)) \to R (x, p)] .

We claim that

G_{e}

is a n-cop-win if and only if

G_{e}

is a computable reflexive connected graph such that

(\forall R \subseteq G_{e} \times G_{e}^{n}) ((ψ_{1} (R) \land ψ_{2} (R)) \to (\forall x, p) R (x, p))

Since this formula is

Π_{1}^{1}

, verifying this claim will complete the proof.

Suppose the offset $Π_{1}^{1}$ formula holds for $G_{e}$ . Since $ψ_{1}$ and $ψ_{2}$ hold for the relation $⪯_{G_{e}}$ , it follows that $x ⪯_{G_{e}} p$ for all x and p. Therefore, by Clarke and MacGillivray’s theorem, $G_{e}$ is k-cop-win.

Suppose $G_{e}$ is k-cop-win and R is a relation such that $ψ_{1} (R)$ and $ψ_{2} (R)$ hold. Since $ψ_{1} (R)$ holds, we have $⩽_{0} \subseteq R$ . Since $ψ_{2} (R)$ holds, it follows that if $⩽_{β} \subseteq R$ for all $β < α$ , then $⩽_{α} \subseteq R$ . Consequently, $⩽_{α} \subseteq R$ for all α, and hence $⪯_{G_{e}} \subseteq R$ . The relation $⪯_{G_{e}}$ is trivial by Clarke and MacGillivray’s theorem, and therefore, $R (x, p)$ holds for all x and p as required.

Footnotes

Acknowledgements

The authors thank the two anonymous referees for their helpful feedback to improve the exposition of this paper.

References

Aigner

Fromme

, A game of cops and robbers, Discrete Applied Mathematics 8 (1984), 1–11. doi:https://doi.org/10.1016/0166-218X(84)90073-8.

Ash

C.J.

Knight

J.F.

, Computable Structures and the Hyperarithmetic Hierarchy, Elsevier, 2000.

Bonato

, An Invitation to Pursuit-Evasion Games and Graph Theory, American Mathematical Society, 2022.

Bonato

Nowakowski

R.J.

, The Game of Cops and Robbers on Graphs, American Mathematical Society, 2011.

Clarke

N.E.

, Constrained Cops and Robbers, Ph.D. Thesis, Dalhousie University, 1999.

Clarke

N.E.

MacGillivray

, Characterizations of k-cop win graphs, Discrete Math 312 (2012), 1421–1425. doi:https://doi.org/10.1016/j.disc.2012.01.002.

Nowakowski

R.J.

Winkler

, Vertex-to-vertex pursuit in a graph, Discrete Mathematics 43 (1983), 235–239. doi:https://doi.org/10.1016/0012-365X(83)90160-7.

Quilliot

, Jeux et pointes fixes sur les graphes, in: Thèses de 3ème cycle, Université de Paris VI, 1978, pp. 131–145.

Soare

R.I.

, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987.

10.

Stahl

R.D.

, Computability and the game of cops and robbers on graphs, Archive for Mathematical Logic 61 (2022), 373–397. doi:https://doi.org/10.1007/s00153-021-00794-3.