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

DOI10.1016/J.TCS.2022.05.015arXiv2110.08898MaRDI QIDQ6380586FDOQ6380586

Authors: Eurinardo R. Costa, N. Martins, Rudini M. Sampaio 

Publication date: 17 October 2021

Abstract: In the $(s,d)$-spy game over a graph $G$, $k$ guards and one spy occupy some vertices of $G$ and, at each turn, the spy may move with speed $s$ (along at most $s$ edges) and each guard may move along one edge. The spy and the guards may occupy the same vertices. The spy wins if she reaches a vertex at distance more than the surveilling distance $d$ from every guard. This game was introduced by Cohen et al. in 2016 and is related to two well-studied games: Cops and robber game and Eternal Dominating game. The guard number $g{n}_{s,d}(G)$ is the minimum number of guards such that the guards have a winning strategy (of controlling the spy) in the graph $G$. In 2018, it was proved that deciding if the spy has a winning strategy is NP-hard for every speed $sgeq2$ and distance $dgeq0$. In this paper, we initiate the investigation of the guard number in grids and in graph products. We obtain a strict upper bound on the strong product of two general graphs and obtain examples with King grids that match this bound and other examples for which the guard number is smaller. We also obtain the exact value of the guard number in the lexicographical product of two general graphs for any distance $dgeq2$. From the algorithmic point of view, we prove a positive result: if the number $k$ of guards is fixed, the spy game is solvable in polynomial XP time $O(n^{3k+2})$ for every speed $sgeq2$ and distance $dgeq0$. In other words, the spy game is XP when parameterized by the number of guards. This XP algorithm is used to obtain an FPT algorithm on the $P_4$-fewness of the graph. As a negative result, we prove that the spy game is W[2]-hard even in bipartite graphs when parameterized by the number of guards, for every speed $sgeq2$ and distance $dgeq0$, extending the hardness result of Cohen et al. in 2018.

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Parameterized complexity, tractability and kernelization (68Q27)

This page was built for publication: Algorithms, hardness and graph products on a pursuit-evasion game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6380586)