Connected Surveillance Game

Abstract : The surveillance game [Fomin 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 observer, can mark a fixed amount of vertices at each turn. The second one controls a surfer that stands at vertices of the graph and can slide along edges. The surfer starts at some initially marked vertex of the graph, its objective is to reach an unmarked node before all nodes of the graph are marked. The 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 et al. also defined the 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 connected surveillance number csn(G) and sn(G) is at most c for any graph G. It is straightforward to show that csn(G) ≤ ∆ sn(G) for any graph G with maximum degree ∆. 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) ≤ sn(G)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 online surveillance game where the observer has no 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 Ω(∆). That is, while interesting, this variant does not help to obtain better upper bounds for the connected variant. We finally answer an open question [Fomin et al., 2012] by proving that deciding if the surveillance number of a digraph with maximum degree 6 is at most 2 is NP-hard.
Type de document :
Article dans une revue
Journal of Theoretical Computer Science (TCS), Elsevier, 2015, 584, pp.131-143
Liste complète des métadonnées


https://hal.inria.fr/hal-01163170
Contributeur : Nicolas Nisse <>
Soumis le : vendredi 12 juin 2015 - 11:32:13
Dernière modification le : mardi 21 février 2017 - 01:09:46
Document(s) archivé(s) le : mardi 25 avril 2017 - 07:23:17

Fichier

Connected-Surveillance-Journal...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01163170, version 1

Collections

Citation

Frédéric Giroire, Ioannis Lamprou, Dorian Mazauric, Nicolas Nisse, Stéphane Pérennes, et al.. Connected Surveillance Game. Journal of Theoretical Computer Science (TCS), Elsevier, 2015, 584, pp.131-143. <hal-01163170>

Partager

Métriques

Consultations de
la notice

249

Téléchargements du document

101