Spy-Game on graphs

Abstract : We define and study the following two-player game on a graph $G$. Let $k \in \mathbb{N}^*$. A set of $k$ {\it guards} is occupying some vertices of $G$ while one {\it spy} is standing at some node. At each turn, first the spy may move along at most $s$ edges, where $s \in \mathbb{N}^*$ is his {\it speed}. Then, each guard may move along one edge. The spy and the guards may occupy same vertices. The spy has to escape the surveillance of the guards, i.e., must reach a vertex at distance more than $d \in \mathbb{N}$ (a predefined distance) from every guard. Can the spy win against $k$ guards? Similarly, what is the minimum distance $d$ such that $k$ guards may ensure that at least one of them remains at distance at most $d$ from the spy? This game generalizes two well-studied games: Cops and robber games (when $s=1$) and Eternal Dominating Set (when $s$ is unbounded). First, we consider the computational complexity of the problem, showing that it is NP-hard and that it is PSPACE-hard in DAGs. Then, we establish tight tradeoffs between the number $k$ of guards and the required distance $d$ when $G$ is a path or a cycle. Our main result is that there exists $\beta>0$ such that $\Omega(n^{1+\beta})$ guards are required to win in any $n \times n$ grid.
Type de document :
[Research Report] RR-8869, Inria. 2016
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

Contributeur : Nicolas Nisse <>
Soumis le : jeudi 25 février 2016 - 20:53:47
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 04:04:17


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01279339, version 1


Nathann Cohen, Mathieu Hilaire, Nicolas Martins, Nicolas Nisse, Stéphane Pérennes. Spy-Game on graphs. [Research Report] RR-8869, Inria. 2016. 〈hal-01279339〉



Consultations de la notice


Téléchargements de fichiers