2021/10/17 by Costa, Eurinardo, Martins, Nicolas, Sampaio, Rudini
#68Q25 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2110.08898
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 and the spy may move along at most s edges. The guards win if, after a finite number of turns, they ensure that the spy always remains at distance at most d from at least one guard. The guard number is the minimum number of guards such that the guards have a winning strategy. In this paper, we investigate the spy game variant in which the guards are placed first, before the spy. We obtain a polynomial time algorithm for every speed s≥ 2 and distance d≥ 0 when the number of guards is a constant, which leads to a fixed parameter tractable algorithm on the P4-fewness of the graph. We also prove that the spy game is NP-hard even in bipartite graphs with bounded diameter, for every speed s≥ 2 and distance d≥ 0.