Spy-game on graphs: Complexity and simple topologies

Nathann Cohen 1 Nicolas Martins 2 Fionn Mc Inerney 3 Nicolas Nisse 3 Stéphane Pérennes 3 Rudini Sampaio 2
1 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)
LRI - Laboratoire de Recherche en Informatique
3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We define and study the following two-player game on a graph G. Let k ∈ N *. A set of k guards is occupying some vertices of G while one spy is standing at some node. At each turn, first the spy may move along at most s edges, where s ∈ N * is his speed. Then, each guard may move along one edge. The spy and the guards may occupy the same vertices. The spy has to escape the surveillance of the guards, i.e., must reach a vertex at distance more than d ∈ 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). We consider the computational complexity of the problem, showing that it is NP-hard (for every speed s and distance d) and that some variant of it is PSPACE-hard in DAGs. Then, we establish tight tradeoffs between the number of guards, the speed s of the spy and the required distance d when G is a path or a cycle.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2018, 725, pp.1 - 15. 〈10.1016/j.tcs.2017.11.015〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01782246
Contributeur : Fionn Mc Inerney <>
Soumis le : mercredi 2 mai 2018 - 13:21:19
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : mardi 25 septembre 2018 - 05:34:42

Fichier

Spygames1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Nathann Cohen, Nicolas Martins, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes, et al.. Spy-game on graphs: Complexity and simple topologies. Theoretical Computer Science, Elsevier, 2018, 725, pp.1 - 15. 〈10.1016/j.tcs.2017.11.015〉. 〈hal-01782246〉

Partager

Métriques

Consultations de la notice

453

Téléchargements de fichiers

54