Cops and Robbers is EXPTIME-complete
William B. Kinnersley · arXiv (Cornell University) · 2013
We investigate the computational complexity of deciding whether k cops can capture a robber on a graph G. In 1995, Goldstein and Reingold conjectured that the problem is EXPTIME-complete when both G and k are part of the input; we prove this conjecture.