×

zbMATH — the first resource for mathematics

Cops and robbers is EXPTIME-complete. (English) Zbl 1307.05155
Summary: We investigate the computational complexity of deciding whether \(k\) cops can capture a robber on a graph \(G\). A. S. Goldstein and E. M. Reingold [Theor. Comput. Sci. 143, No. 1, 93–112 (1995; Zbl 0873.68152)] conjectured that the problem is EXPTIME-complete when both \(G\) and \(k\) are part of the input; we prove this conjecture.

MSC:
05C57 Games on graphs (graph-theoretic aspects)
91A43 Games involving graphs
91A24 Positional games (pursuit and evasion, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aigner, M.; Fromme, M., A game of cops and robbers, Discrete Appl. Math., 8, 1-12, (1984) · Zbl 0539.05052
[2] Berarducci, A.; Intrigila, B., On the cop number of a graph, Adv. Appl. Math., 14, 389-403, (1993) · Zbl 0801.90150
[3] Bonato, A.; Chiniforooshan, E., Pursuit and evasion from a distance: algorithms and bounds, (Proceedings of Workshop on Analytic Algorithms and Combinatorics, ANALCO’09, (2009))
[4] Bonato, A.; Nowakowski, R. J., The game of cops and robbers on graphs, (2011), American Mathematical Society Providence, RI · Zbl 1298.91004
[5] Clarke, N. E.; MacGillivray, G., Characterizations of k-copwin graphs, Discrete Math., 312, 1421-1425, (2012) · Zbl 1235.91024
[6] Fomin, F. V.; Golovach, P. A.; Kratochvíl, J.; Nisse, N.; Suchan, K., Pursuing a fast robber on a graph, Theoret. Comput. Sci., 411, 1167-1181, (2010) · Zbl 1192.91027
[7] Fomin, F. V.; Golovach, P. A.; Prałat, P., Cops and robber with constraints, SIAM J. Discrete Math., 26, 571-590, (2012) · Zbl 1248.05120
[8] Goldstein, A. S.; Reingold, E. M., The complexity of pursuit on a graph, Theoret. Comput. Sci., 143, 93-112, (1995) · Zbl 0873.68152
[9] Hahn, G.; MacGillivray, G., A characterization of k-cop-win graphs and digraphs, Discrete Math., 306, 2492-2497, (2006) · Zbl 1201.91018
[10] Homer, S., Structural properties of complete problems for exponential time, (Complexity Theory Retrospective, II, (1997), Springer New York), 135-153 · Zbl 0880.68040
[11] Isaza, A.; Lu, J.; Bulitko, V.; Greiner, R., A cover-based approach to multi-agent moving target pursuit, (Proceedings of The 4th Conference on Artificial Intelligence and Interactive Digital Entertainment, (2008))
[12] Mamino, M., On the computational complexity of a game of cops and robbers, Theoret. Comput. Sci., 477, 48-56, (2013) · Zbl 1290.68050
[13] Moldenhauer, C.; Sturtevant, N., Evaluating strategies for running from the cops, (Proceedings of IJCAI, (2009))
[14] Nowakowski, R. J.; Winkler, P., Vertex-to-vertex pursuit in a graph, Discrete Math., 43, 235-239, (1983) · Zbl 0508.05058
[15] Quilliot, A., Jeux et pointes fixes sur LES graphes, 131-145, (1978), Université de Paris VI, Thèse de 3ème cycle
[16] Stockmeyer, L.; Chandra, A., Provably difficult combinatorial games, SIAM J. Comput., 8, 2, 151-174, (1979) · Zbl 0421.68044
[17] West, D. B., Introduction to graph theory, (2001), Prentice Hall
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.