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.
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01279339
Contributor : Nicolas Nisse <>
Submitted on : Thursday, February 25, 2016 - 8:53:47 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Sunday, November 13, 2016 - 4:04:17 AM

File

RR-8869.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

744

Files downloads

382