DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

D. Bokal

Drago Bokal

Faculty of Natural Sciences and Mathematics
University of Maribor
Maribor, Slovenia

email: drago.bokal@um.si

J. Jerebic

Janja Jerebic

Faculty of Organizational Sciences
University of Maribor
Kranj, Slovenia

email: janja.jerebic@um.si

Title:

Guarding a subgraph as a tool in pursuit-evasion games

PDF

Source:

Discussiones Mathematicae Graph Theory 42(1) (2022) 123-138

Received: 2016-10-20 , Revised: 2019-08-05 , Accepted: 2019-08-05 , Available online: 2019-10-16 , https://doi.org/10.7151/dmgt.2244

Abstract:

Pursuit-evasion games study the number of cops needed to capture the robber in a game played on a graph, in which the cops and the robber move alternatively to neighbouring vertices, and the robber is captured if a cop steps on the vertex the robber is in. A common tool in analyzing this cop number of a graph is a cop moving along a shortest path in a graph, thus preventing the robber to step onto this path. We generalize this approach by introducing a shadow of the robber, the maximal set of vertices from which the cop parries the protected subgraph. In this context, the robber becomes an intruder and the cop becomes the guard. We show that the shadow can be computed in polynomial time, implying polynomial time algorithms for computing both a successful guard as well as a successful intruder, whichever exists. Furthermore, we show that shadow function generalizes the concept of graph retractions. In some cases, this implies a polynomially computable certification of the negative answer to the NP-complete problem of existence of a retraction to a given subgraph.

Keywords:

pursuit-evasion game, graph searching, guarding, shadow function, graph retraction

References:

  1. M. Aigner and M. Fromme, A game of cops and robbers, Discrete Appl. Math. 8 (1984) 1–12.
    https://doi.org/10.1016/0166-218X(84)90073-8
  2. B. Alspach, Searching and sweeping graphs: A brief survey, Matematiche (Catania) 59 (2004) 5–37.
  3. T. Andreae, On a pursuit game played on graphs for which a minor is excluded, J. Combin. Theory Ser. B 41 (1986) 37–47.
    https://doi.org/10.1016/0095-8956(86)90026-2
  4. A. Bonato and B. Yang, Graph searching and related problems, in: Handbook of Combinatorial Optimization, (Springer, New York 2013) 1511–1558.
    https://doi.org/10.1007/978-1-4419-7997-1_76
  5. E. Chiniforooshan, A better bound for the cop number of general graphs, J. Graph Theory 58 (2008) 45–48.
    https://doi.org/10.1002/jgt.20291
  6. E.J. Cockayne, P.J.P. Grobler, W.R. Gründlingh, J. Munganga and J.H. van Vuuren, Protection of a graph, Util. Math. 67 (2005) 19–32.
  7. T. Feder and P. Hell, List homomorphisms to reflexive graphs, J. Combin. Theory Ser. B 72 (1998) 236–250.
    https://doi.org/10.1006/jctb.1997.1812
  8. F.V. Fomin, P.A. Golovach, A. Hall, M. Mihalák, E. Vicari and P. Widmayer, How to guard a graph?, Algorithmica 61 (2011) 839–856.
    https://doi.org/10.1007/s00453-009-9382-4
  9. F.V. Fomin, P.A. Golovach and D. Lokshtanov, Guard games on graphs: Keep the intruder out, Theoret. Comput. Sci. 412 (2011) 6484–6497.
    https://doi.org/10.1016/j.tcs.2011.08.024
  10. G. Hahn and G. MacGillivray, A note on $k$-cop, $l$-robber games on graphs, Discrete Math. 306 (2006) 2492–2497.
    https://doi.org/10.1016/j.disc.2005.12.038
  11. H. Nagamochi, Cop-robber guarding game with cycle robber region, in: 3rd International Workshop on Frontiers in Algorithmics, Lecture Notes in Comput. Sci. 5598, (Springer-Verlag, Berlin 2009) 74–84.
  12. R. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, Discrete Math. 43 (1983) 235–239.
    https://doi.org/10.1016/0012-365X(83)90160-7
  13. A. Quilliot, A short note about pursuit games played on a graph with a given genus, J. Combin. Theory Ser. B 38 (1985) 89–92.
    https://doi.org/10.1016/0095-8956(85)90093-0
  14. T.D. Parsons, Pursuit-evasion in a graph, in: Theory and Applications of Graphs, Y. Alavi and D.R. Lick (Ed(s)), (Lecture Notes in Math. 642 Springer-Verlag, Berlin) 1978, 426–441.
    https://doi.org/10.1007/BFb0070400
  15. T. Reddy, S. Krishna and P. Rangan, The guarding problem–-complexity and approximation, in: Proceedings of IWOCA, 2009, J. Fiala, J. Kratochvíl and M. Miller (Ed(s)), (Lecture Notes in Comput. Sci. 5874 2009) 460–470.
    https://doi.org/10.1007/978-3-642-102217-2$_-$45
  16. B. Schröder, The cop number of a graph is bounded by $\left\lfloor\frac{3}{2} \textrm{genus}(G)\right\rfloor+3$, in: Categorical Perspectives, Trends Math., (Birkhäuser, Boston 2001) 243–263.
    https://doi.org/10.1007/978-1-4612-1370-3_14
  17. R. Šámal, R. Stolař and T. Valla, Complexity of the cop and robber guarding game, in: Proceedings of IWOCA 2011, (Lecture Notes in Comput. Sci. 7056 2011) 361–373.
    https://doi.org/10.1007/978-3-642-25011-8_29
  18. R. Šámal and T. Valla, The guarding game is E-complete, Theoret. Comput. Sci. 521 (2014) 92–106.
    https://doi.org/10.1016/j.tcs.2013.11.034
Close