Computing strategies for multiple cops on infinite graphs

Article type: Research Article

Authors: McLeod, Alexa^{a; *} | Solomon, Reed^b

Affiliations: [a] Department of Mathematics, University of Connecticut, CT, USA | [b] Department of Mathematics, University of Connecticut, CT, USA

Correspondence: [*] Corresponding author. [email protected].

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 Π11-complete.

Keywords: Computability theory, game of cops and robbers

DOI: 10.3233/COM-240016

Journal: Computability, vol. Pre-press, no. Pre-press, pp. 1-8, 2024