×

Lower bounds for the capture time: linear, quadratic, and beyond. (English) Zbl 1471.91060

Scheideler, Christian (ed.), Structural information and communication complexity. 22nd international colloquium, SIROCCO 2015, Montserrat, Spain, July 14–16, 2015. Post-proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9439, 342-356 (2015).
Summary: In the classical game of Cops and Robbers on graphs, the capture time is defined by the least number of moves needed to catch all robbers with the smallest amount of cops that suffice. While the case of one cop and one robber is well understood, it is an open question how long it takes for multiple cops to catch multiple robbers. We show that capturing \(\ell \in {\mathcal{O}}\left(n\right)\) robbers can take \(\Omega\left(\ell \cdot n\right)\) time, inducing a capture time of up to \(\Omega\left(n^2\right)\). For the case of one cop, our results are asymptotically optimal. Furthermore, we consider the case of a superlinear amount of robbers, where we show a capture time of \(\Omega \left(n^2 \cdot \log\left(\ell/n\right) \right)\).
For the entire collection see [Zbl 1325.68023].

MSC:

91A43 Games involving graphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91A24 Positional games (pursuit and evasion, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aigner, M., Fromme, M.: A Game of Cops and Robbers. Discrete Applied Mathematics 8(1), 1–12 (1984) · Zbl 0539.05052 · doi:10.1016/0166-218X(84)90073-8
[2] Alspach, B.: Sweeping and Searching in Graphs: a Brief Survey. Matematiche 59, 5–37 (2006) · Zbl 1195.05019
[3] Berarducci, A., Intrigila, B.: On the Cop Number of a Graph. Advances in Applied Mathematics 14(4), 389–403 (1993) · Zbl 0801.90150 · doi:10.1006/aama.1993.1019
[4] Bonato, A., Chiniforooshan, E.: Pursuit and evasion from a distance: algorithms and bounds. In: Proceedings of the Sixth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pp. 1–10. SIAM (2009) · doi:10.1137/1.9781611972993.1
[5] Bonato, A., Golovach, P.A., Hahn, G., Kratochvíl, J.: The Capture Time of a Graph. Discrete Mathematics 309(18), 5588–5595 (2009) · Zbl 1177.91056 · doi:10.1016/j.disc.2008.04.004
[6] Bonato, A., Gordinowicz, P., Kinnersley, B., Prałat, P.: The Capture Time of the Hypercube. Electr. J. Comb. 20(2), P24 (2013) · Zbl 1266.05096
[7] Bonato, A., Nowakowski, R.J.: The Game of Cops and Robbers on Graphs. Student Mathematical Library, vol. 61. American Mathematical Society, Providence (2011) · Zbl 1298.91004 · doi:10.1090/stml/061
[8] Bonato, A., Yang, B.: Graph searching and related problems. In: Handbook of Combinatorial Optimization, pp. 1511–1558. Springer, New York (2013) · doi:10.1007/978-1-4419-7997-1_76
[9] Breisch, R.: An Intuitive Approach to Speleotopology. Southwestern Cavers 6(5), 72–78 (1967)
[10] Clarke, N.E., MacGillivray, G.: Characterizations of k-copwin Graphs. Discrete Mathematics 312(8), 1421–1425 (2012) · Zbl 1235.91024 · doi:10.1016/j.disc.2012.01.002
[11] Deo, N., Nikoloski, Z.: The Game of Cops and Robbers on Graphs: a Model for Quarantining Cyber Attacks. Congressus Numerantium, 193–216 (2003) · Zbl 1091.68555
[12] Frankl, P.: Cops and Robbers in Graphs with Large Girth and Cayley Graphs. Discrete Appl. Math. 17(3), 301–305 (1987) · Zbl 0624.05041 · doi:10.1016/0166-218X(87)90033-3
[13] Frieze, A.M., Krivelevich, M., Loh, P.-S.: Variations on Cops and Robbers. Journal of Graph Theory 69(4), 383–402 (2012) · Zbl 1243.05165 · doi:10.1002/jgt.20591
[14] Gavenciak, T.: Cop-win Graphs with Maximum Capture-time. Discrete Mathematics 310(10–11), 1557–1563 (2010) · Zbl 1186.91051 · doi:10.1016/j.disc.2010.01.015
[15] Hahn, G.: Cops, Robbers and Graphs. Tatra Mt. Math. Publ. 36(163), 163–176 (2007) · Zbl 1164.05063
[16] Kinnersley, W.B.: Cops and Robbers is EXPTIME-complete. J. Comb. Theory, Ser. B 111, 201–220 (2015) · Zbl 1307.05155 · doi:10.1016/j.jctb.2014.11.002
[17] Kosowski, A., Li, B., Nisse, N., Suchan, K.: k-Chordal graphs: from cops and robber to compact routing via treewidth. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 610–622. Springer, Heidelberg (2012) · Zbl 1318.68127 · doi:10.1007/978-3-642-31585-5_54
[18] Lu, L., Peng, X.: On Meyniel’s Conjecture of the Cop Number. Journal of Graph Theory 71(2), 192–205 (2012) · Zbl 1248.05121 · doi:10.1002/jgt.20642
[19] Mehrabian, A.: The Capture Time of Grids. Discrete Mathematics 311(1), 102–105 (2011) · Zbl 1203.91039 · doi:10.1016/j.disc.2010.10.002
[20] Moon, J.W.: On the Diameter of a Graph. Michigan Math. J. 12(3), 349–351 (1965) · Zbl 0134.19603 · doi:10.1307/mmj/1028999370
[21] Nowakowski, R.J., Winkler, P.: Vertex-to-vertex Pursuit in a Graph. Discrete Mathematics 43(2-3), 235–239 (1983) · Zbl 0508.05058 · doi:10.1016/0012-365X(83)90160-7
[22] Parsons, T.D.: Pursuit-evasion in a graph. In: Alavi, Y., Lick, D.R. (eds.) AII 1992. LNCS, vol. 642, pp. 426–441. Springer, Heidelberg (1992)
[23] Parsons, T.D.: The search number of a connected graph. In: Proc. 9th Southeast. Conf. on Combinatorics, Graph Theory, and Computing (1978) · Zbl 0418.05022
[24] Prałat, P.: When Does a Random Graph Have a Constant Cop Number. Australasian Journal of Combinatorics 46, 285–296 (2010) · Zbl 1196.05089
[25] Quilliot, A.: Jeux et Pointes Fixes sur les Graphes. Ph.D. thesis, Universite de Paris VI (1978)
[26] Scott, A., Sudakov, B.: A Bound for the Cops and Robbers Problem. SIAM J. Discrete Math. 25(3), 1438–1442 (2011) · Zbl 1237.05132 · doi:10.1137/100812963
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.