zbMATH — the first resource for mathematics

Bounds on the length of a game of cops and robbers. (English) Zbl 1392.05082
Summary: In the game of Cops and Robbers, a team of cops attempts to capture a robber on a graph \(G\). All players occupy vertices of \(G\). The game operates in rounds; in each round the cops move to neighboring vertices, after which the robber does the same. The minimum number of cops needed to guarantee capture of a robber on \(G\) is the cop number of \(G\), denoted \(c(G)\), and the minimum number of rounds needed for them to do so is the capture time. It has long been known that the capture time of an \(n\)-vertex graph with cop number \(k\) is \(O(n^{k + 1})\). More recently, A. Bonato et al. [Discrete Math. 309, No. 18, 5588–5595 (2009; Zbl 1177.91056)] and T. Gavenčiak [Discrete Math. 310, No. 10–11, 1557–1563 (2010; Zbl 1186.91051)] showed that for \(k = 1\), this upper bound is not asymptotically tight: for graphs with cop number 1, the cop can always win within \(n - 4\) rounds. In this paper, we show that the upper bound is tight when \(k \geq 2\): for fixed \(k \geq 2\), we construct arbitrarily large graphs \(G\) having capture time at least \(\left(\frac{\left|V(G)\right|}{40 k^4}\right)^{k + 1}\).
In the process of proving our main result, we establish results that may be of independent interest. In particular, we show that the problem of deciding whether \(k\) cops can capture a robber on a directed graph is polynomial-time equivalent to deciding whether \(k\) cops can capture a robber on an undirected graph. As a corollary of this fact, we obtain a relatively short proof of a major conjecture of A. S. Goldstein and E. M. Reingold [Theor. Comput. Sci. 143, No. 1, 93–112 (1995; Zbl 0873.68152)], which was recently proved through other means [W. B. Kinnersley, J. Comb. Theory, Ser. B 111, 201–220 (2015; Zbl 1307.05155)]. We also show that \(n\)-vertex strongly-connected directed graphs with cop number 1 can have capture time \(\varOmega(n^2)\), thereby showing that the result of A. Bonato et al. [loc. cit.] does not extend to the directed setting.

05C57 Games on graphs (graph-theoretic aspects)
91A43 Games involving graphs
91A24 Positional games (pursuit and evasion, etc.)
Full Text: DOI arXiv
[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.; Nowakowski, R. J., The game of cops and robbers on graphs, (2011), American Mathematical Society Providence, Rhode Island · Zbl 1298.91004
[4] Bonato, A.; Golovach, P.; Hahn, G.; Kratochvíl, J., The capture time of a graph, Discrete Math., 309, 5588-5595, (2009) · Zbl 1177.91056
[5] Bonato, A.; Gordinowicz, P.; Kinnersley, W. B.; Prałat, P., The capture time of the hypercube, Electron. J. Combin., 20, Paper P24, (2013) · Zbl 1266.05096
[6] Bonato, A.; Pérez-Giménez, X.; Prałat, P.; Reiniger, B., The game of overprescribed cops and robbers played on graphs, Graphs Combin., (2017) · Zbl 1371.05179
[7] S. Brandt, Y. Emek, J. Uitto, R. Wattenhoffer, A tight lower bound for the capture time of the cops and robbers game, in: Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP, track A), pages 82:1-82:13, 2017.
[8] Förster, K.-T.; Nuridini, R.; Uitto, J.; Wattenhoffer, R., Lower bounds for the capture time: linear, quadratic, and beyond, Lecture Notes in Comput. Sci., 9439, 342-356, (2015) · Zbl 06527700
[9] Frieze, A.; Krivilevich, M.; Loh, P., Variations on cops and robbers, J. Graph Theory, 69, 4, 383-402, (2012) · Zbl 1243.05165
[10] Gavenčiak, T., Cop-win graphs with maximum capture-time, Discrete Math., 310, 1557-1563, (2010) · Zbl 1186.91051
[11] Goldstein, A. S.; Reingold, E. M., The complexity of pursuit on a graph, Theoret. Comput. Sci., 143, 93-112, (1995) · Zbl 0873.68152
[12] Kinnersley, W. B., Cops and robbers is EXPTIME-complete, J. Combin. Theory Ser. B, 111, 201-220, (2015) · Zbl 1307.05155
[13] Loh, P.; Oh, S., Cops and robbers on planar-directed graphs, J. Graph Theory, 86, 3, 329-340, (2017) · Zbl 1375.05172
[14] Mamino, M., On the computational complexity of a game of cops and robbers, Theoret. Comput. Sci., 477, 48-56, (2013) · Zbl 1290.68050
[15] Mehrabian, A., The capture time of grids, Discrete Math., 311, 102-105, (2011) · Zbl 1203.91039
[16] Nowakowski, R. J.; Winkler, P., Vertex-to-vertex pursuit in a graph, Discrete Math., 43, 235-239, (1983) · Zbl 0508.05058
[17] Pisantechakool, P., On the capture time of cops and robbers game on a planar graph, (Chan, T. H.; Li, M.; Wang, L., Combinatorial Optimization and Applications. COCOA, Lecture Notes in Computer Science, (2016)), 10043
[18] Quilliot, A., Jeux et pointes fixes sur LES graphes, 131-145, (1978), Univerité de Paris VI, (Thèse de 3ème Cycle)
[19] 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.