×

Pursuing a fast robber on a graph. (English) Zbl 1192.91027

The Cops and Robbers game as originally defined independently by Quilliot and by Nowakowski and Winkler in the 1980s has been much studied, but very few results pertain to the algorithmic and complexity aspects of it. In this paper it is proved that computing the minimum number of cops that are guaranteed to catch a robber on a given graph is NP-hard and that the parameterized version of the problem is \(W[2]\)-hard; the proof extends to the case where the robber moves \(s\) time faster than the cops. It is shown that on split graphs, the problem is polynomially solvable if \(s = 1\) but is NP-hard if \(s = 2\). It is also proved that on graphs of bounded cliquewidth the problem is polynomially solvable for \(s < 3\). Finally, it is shown that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops.

MSC:

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

References:

[1] Adachi, A.; Iwata, S.; Kasai, T., Some combinatorial game problems require \(\Omega(n^k)\) time, J. ACM, 31, 361-376 (1984) · Zbl 0631.68036
[2] Aigner, M.; Fromme, M., A game of cops and robbers, Discrete Appl. Math., 8, 1-11 (1984) · Zbl 0539.05052
[3] Alspach, B., Searching and sweeping graphs: A brief survey, Matematiche (Catania), 59, 5-37 (2006) · Zbl 1195.05019
[4] Andreae, T., Note on a pursuit game played on graphs, Discrete Appl. Math., 9, 111-115 (1984) · Zbl 0548.05056
[5] Andreae, T., On a pursuit game played on graphs for which a minor is excluded, J. Combin. Theory Ser. B, 41, 37-47 (1986) · Zbl 0641.90110
[6] Berarducci, A.; Intrigila, B., On the cop number of a graph, Adv. in Appl. Math., 14, 389-403 (1993) · Zbl 0801.90150
[7] Bodlaender, H. L., A partial \(k\)-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1-45 (1998) · Zbl 0912.68148
[8] Bollobás, B., (Extremal Graph Theory. Extremal Graph Theory, London Mathematical Society Monographs, vol. 11 (1978), Academic Press Inc., Harcourt Brace Jovanovich Publishers: Academic Press Inc., Harcourt Brace Jovanovich Publishers London)
[9] B. Bollobás, G. Kun, I. Leader, Cops and robbers in a random graph. ArXiv e-prints, http://arxiv.org/abs/0805.2709v1; B. Bollobás, G. Kun, I. Leader, Cops and robbers in a random graph. ArXiv e-prints, http://arxiv.org/abs/0805.2709v1
[10] Brandstädt, A.; Le, V. B.; Spinrad, J. P., (Graph Classes: A Survey. Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications (1999), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA)
[11] Chiniforooshan, E., A better bound for the cop number of general graphs, J. Graph Theory, 58, 1, 45-48 (2008) · Zbl 1207.05138
[12] Corneil, D. G.; Olariu, S.; Stewart, L., Asteroidal triple-free graphs, SIAM J. Discrete Math., 10, 399-430 (1997) · Zbl 0884.05075
[13] Courcelle, B.; Engelfriet, J.; Rozenberg, G., Context-free handle-rewriting hypergraph grammars, (Ehrig, H.; Kreowski, H.-J.; Rozenberg, G., Graph-Grammars and Their Application to Computer Science. Graph-Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 532 (1990), Springer), 253-268 · Zbl 0765.68084
[14] Diestel, R., Graph Theory, third edition (2005), Springer-Verlag
[15] Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer-Verlag: Springer-Verlag New York · Zbl 0914.68076
[16] Fitzpatrick, S. L.; Nowakowski, R. J., Copnumber of graphs with strong isometric dimension two, Ars Combin., 59, 65-73 (2001) · Zbl 1066.05118
[17] Flum, J.; Grohe, M., (Parameterized Complexity Theory. Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series (2006), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1087.68034
[18] Fomin, F. V.; Golovach, P. A.; Kratochvíl, J., On tractability of Cops and Robbers game, (Proceedings of the 5th IFIP International Conference on Theoretical Computer Science. Proceedings of the 5th IFIP International Conference on Theoretical Computer Science, TCS 2008. Proceedings of the 5th IFIP International Conference on Theoretical Computer Science. Proceedings of the 5th IFIP International Conference on Theoretical Computer Science, TCS 2008, Computer Science, vol. 237 (2008), Springer: Springer Boston), 171-185
[19] Fomin, F. V.; Thilikos, D. M., An annotated bibliography on guaranteed graph searching, Theoretical Computer Science, 399, 236-245 (2008) · Zbl 1160.68007
[20] Frankl, P., Cops and robbers in graphs with large girth and Cayley graphs, Discrete Appl. Math., 17, 301-305 (1987) · Zbl 0624.05041
[21] Frankl, P., On a pursuit game on Cayley graphs, Combinatorica, 7, 67-70 (1987) · Zbl 0621.05017
[22] Goldstein, A. S.; Reingold, E. M., The complexity of pursuit on a graph, Theoret. Comput. Sci., 143, 93-112 (1995) · Zbl 0873.68152
[23] Gustedt, J., On the pathwidth of chordal graphs, Discrete Appl. Math., 45, 233-248 (1993) · Zbl 0798.68134
[24] Hahn, G., Cops, robbers and graphs, Tatra Mt. Math. Publ., 36, 163-176 (2007) · Zbl 1164.05063
[25] Hahn, G.; MacGillivray, G., A note on \(k\)-cop, \(l\)-robber games on graphs, Discrete Math., 306, 2492-2497 (2006) · Zbl 1201.91018
[26] Hamidoune, Y. O., On a pursuit game on Cayley digraphs, European J. Combin., 8, 289-295 (1987) · Zbl 0639.05026
[27] Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity, J. Comput. System Sci., 63, 512-530 (2001) · Zbl 1006.68052
[28] K.M. Krishnan, R. Singh, L.S. Chandran, P. Shankar, A combinatorial family of near regular LDPC codes. ArXiv Computer Science e-prints, cs/0609146, (2006); K.M. Krishnan, R. Singh, L.S. Chandran, P. Shankar, A combinatorial family of near regular LDPC codes. ArXiv Computer Science e-prints, cs/0609146, (2006)
[29] Maamoun, M.; Meyniel, H., On a game of policemen and robber, Discrete Appl. Math., 17, 307-309 (1987) · Zbl 0615.05049
[30] Neufeld, S.; Nowakowski, R. J., A vertex-to-vertex pursuit game played with disjoint sets of edges, (Finite and Infinite Combinatorics in Sets and Logic. Finite and Infinite Combinatorics in Sets and Logic, Banff, AB, 1991. Finite and Infinite Combinatorics in Sets and Logic. Finite and Infinite Combinatorics in Sets and Logic, Banff, AB, 1991, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 411 (1993), Kluwer Acad. Publ.: Kluwer Acad. Publ. Dordrecht), 299-312 · Zbl 0845.05092
[31] Niedermeier, R., (Invitation to Fixed-parameter Algorithms. Invitation to Fixed-parameter Algorithms, Oxford Lecture Series in Mathematics and its Applications, vol. 31 (2006), Oxford University Press: Oxford University Press Oxford) · Zbl 1095.68038
[32] Nisse, N.; Suchan, K., (Fast Robber in Planar Graphs. Fast Robber in Planar Graphs, Proceedings of the 34th Workshop on Graph Theoretic Concepts in Computer Science (WG 2008). Fast Robber in Planar Graphs. Fast Robber in Planar Graphs, Proceedings of the 34th Workshop on Graph Theoretic Concepts in Computer Science (WG 2008), Springer-Verlag Lecture Notes in Computer Science, vol. 5344 (2008)), 312-323 · Zbl 1202.68286
[33] Nowakowski, R.; Winkler, P., Vertex-to-vertex pursuit in a graph, Discrete Math., 43, 235-239 (1983) · Zbl 0508.05058
[34] Peng, S.-L.; Ko, M.-T.; Ho, C.-W.; Hsu, T.-s.; Tang, C. Y., Graph searching on some subclasses of chordal graphs, Algorithmica, 27, 395-426 (2000) · Zbl 0955.05074
[35] Quilliot, A., A short note about pursuit games played on a graph with a given genus, J. Combin. Theory Ser. B, 38, 89-92 (1985) · Zbl 0586.90104
[36] Quilliot, A., Some results about pursuit games on metric spaces obtained through graph theory techniques, European J. Combin., 7, 55-66 (1986) · Zbl 0615.90108
[37] Raman, V.; Saurabh, S., Short cycles make \(w\)-hard problems hard: Fpt algorithms for \(w\)-hard problems in graphs with no short cycles, Algorithmica, 52, 203-225 (2008) · Zbl 1170.68019
[38] R. Raz, S. Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, in STOC, 1997, pp. 475-484; R. Raz, S. Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, in STOC, 1997, pp. 475-484 · Zbl 0963.68175
[39] Schroeder, B. S.W., The copnumber of a graph is bounded by \(\lfloor \frac{3}{2} \text{genus}(G) \rfloor + 3\), (Categorical perspectives. Categorical perspectives, Kent, OH, 1998. Categorical perspectives. Categorical perspectives, Kent, OH, 1998, Trends Math. (2001), Birkhäuser Boston: Birkhäuser Boston Boston, MA), 243-263 · Zbl 0983.05030
[40] Seymour, P. D.; Thomas, R., Graph searching and a min-max theorem for tree-width, J. Combin. Theory Ser. B, 58, 22-33 (1993) · Zbl 0795.05110
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.