Algorithms, hardness and graph products on a pursuit-evasion game

Eurinardo Costa, Nicolas Martins, Rudini Sampaio

In the $(s,d)$-spy game over a graph, introduced by Cohen et al. in 2016, one spy and $k$ guards occupy vertices of a graph and, at each turn, each guard may move along one edge an…