Reproducing the k-copwin Algorithm: Theory vs. Implementation
arXiv:2607.13271
The paper details a Python implementation of the 2022 k‑copwin algorithm for the Cops and Robbers game on graphs, clarifying its operation and assessing practical deployment considerations.
Abstract
Cops and Robbers is a well-studied pursuit-evasion game that provides insights into graph theory and theoretical computing. A central question is determining the minimum number of cops required to capture the robber, known as the cop number. We focus on reproducing an algorithm proposed by Petr, Portier, and Versteegen in 2022, which efficiently determines whether a graph is -copwin. This paper presents a Python implementation of the -copwin algorithm. In this work, we present our implementation in detail, clarify key aspects of the algorithm, and discuss its implications for future practical deployments.