Cops and Robbers is EXPTIME-complete
classification
🧮 math.CO
cs.CCcs.DM
keywords
copsexptime-completecapturecomplexitycomputationalconjectureconjectureddeciding
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.