Connected Surveillance Game

Abstract : The \emph{surveillance game} [Fomin \textit{et al.}, 2012] models the problem of web-page prefetching as a pursuit evasion game played on a graph. This two-player game is played turn-by-turn. The first player, called the \emph{observer}, can mark a fixed amount of vertices at each turn. The second one controls a \emph{surfer} that stands at vertices of the graph and can slide along edges. The surfer starts at some initially marked vertex of the graph, her objective is to reach an unmarked node before all nodes of the graph are marked. The \emph{surveillance number} $\sn(G)$ of a graph $G$ is the minimum amount of nodes that the observer has to mark at each turn ensuring it wins against any surfer in $G$. Fomin \textit{et al.} also defined the \emph{connected surveillance game} where the observer must ensure that marked nodes always induce a connected subgraph. They ask what is the cost of connectivity, i.e., is there a constant $c>0$ such that the ratio between the \emph{connected surveillance number} $\csn(G)$ and $\sn(G)$ is at most $c$ for any graph $G$. It is straightforward to show that $\csn(G) \leq \Delta \sn(G)$ for any graph $G$ with maximum degree $\Delta$. Moreover, it has been shown that there are graphs $G$ for which $\csn(G)=\sn(G)+1$. In this paper, we investigate the question of the cost of the connectivity. We first provide new non-trivial upper and lower bounds for the cost of connectivity in the surveillance game. More precisely, we present a family of graphs $G$ such that $\csn(G)>\sn(G)+1$. Moreover, we prove that $\csn(G) \leq \sn(G) \sqrt{n}$ for any $n$-node graph $G$. While the gap between these bounds remains huge, it seems difficult to reduce it. We then define the \emph{online surveillance game} where the observer has no \emph{a priori} knowledge of the graph topology and discovers it little-by-little. This variant, which fits better the prefetching motivation, is a restriction of the connected variant. Unfortunately, we show that no algorithm for solving the online surveillance game has competitive ratio better than $\Omega(\Delta)$. That is, while interesting by itself, this variant does not help to obtain better upper bounds for the connected variant.
Document type :
[Research Report] RR-8297, 2013, pp.22
Contributor : Ronan Pardo Soares <>
Submitted on : Friday, May 3, 2013 - 3:29:27 PM
Last modification on : Sunday, May 5, 2013 - 11:58:57 AM




  • HAL Id : hal-00820271, version 1



Frédéric Giroire, Dorian Mazauric, Nicolas Nisse, Stéphane Pérennes, Ronan Pardo Soares. Connected Surveillance Game. [Research Report] RR-8297, 2013, pp.22. <hal-00820271>




Consultation de
la notice


Téléchargement du document