Cohen, Nathann ;
Hilaire, Mathieu ;
Martins, Nícolas A. ;
Nisse, Nicolas ;
Pérennes, Stéphane
SpyGame on Graphs
Abstract
We define and study the following twoplayer game on a graph G. Let k in 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 in N^* is his 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 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 wellstudied 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 NPhard and that it is PSPACEhard in DAGs. Then, we establish tight tradeoffs between the number 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*n grid.
BibTeX  Entry
@InProceedings{cohen_et_al:LIPIcs:2016:5878,
author = {Nathann Cohen and Mathieu Hilaire and N{\'i}colas A. Martins and Nicolas Nisse and St{\'e}phane P{\'e}rennes},
title = {{SpyGame on Graphs}},
booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)},
pages = {10:110:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770057},
ISSN = {18688969},
year = {2016},
volume = {49},
editor = {Erik D. Demaine and Fabrizio Grandoni},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5878},
URN = {urn:nbn:de:0030drops58782},
doi = {10.4230/LIPIcs.FUN.2016.10},
annote = {Keywords: graph, twoplayer games, cops and robber games, complexity}
}
2016
Keywords: 

graph, twoplayer games, cops and robber games, complexity 
Seminar: 

8th International Conference on Fun with Algorithms (FUN 2016)

Issue date: 

2016 
Date of publication: 

2016 