Spy-Game on graphs

4 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
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 :
Rapport
[Research Report] RR-8869, Inria. 2016
Domaine :

https://hal.inria.fr/hal-01279339
Contributeur : Nicolas Nisse <>
Soumis le : jeudi 25 février 2016 - 20:53:47
Dernière modification le : samedi 18 février 2017 - 01:20:42
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 04:04:17

Fichier

RR-8869.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

• HAL Id : hal-01279339, version 1

Citation

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

348

Téléchargements du document