Geodesic
Guarding a Subgraph as a Tool in Pursuit-Evasion Games
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 123-138

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2022_42_1_a8,
     author = {Bokal, Drago and Jerebic, Janja},
     title = {Guarding a {Subgraph} as a {Tool} in {Pursuit-Evasion} {Games}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {123--138},
     publisher = {mathdoc},
     volume = {42},
     number = {1},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a8/}
}
TY  - JOUR
AU  - Bokal, Drago
AU  - Jerebic, Janja
TI  - Guarding a Subgraph as a Tool in Pursuit-Evasion Games
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 123
EP  - 138
VL  - 42
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a8/
LA  - en
ID  - DMGT_2022_42_1_a8
ER  - 
%0 Journal Article
%A Bokal, Drago
%A Jerebic, Janja
%T Guarding a Subgraph as a Tool in Pursuit-Evasion Games
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 123-138
%V 42
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a8/
%G en
%F DMGT_2022_42_1_a8
Bokal, Drago; Jerebic, Janja. Guarding a Subgraph as a Tool in Pursuit-Evasion Games. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 123-138. http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a8/