Connected Surveillance GameReport as inadecuate

Connected Surveillance Game - Download this document for free, or read online. Document in PDF available to download.

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués 2 UoA - University of Athens 3 LIF - Laboratoire d-informatique Fondamentale de Marseille 4 ParGO - Parallelism, Graphs and Optimization Research Group

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 snG 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 csnG and snG is at most c for any graph G. It is straightforward to show that csnG ≤ ∆ snG for any graph G with maximum degree ∆. Moreover, it has been shown that there are graphs G for which csnG = snG + 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 csnG > snG + 1. Moreover, we prove that csnG ≤ snGn 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.

Keywords : Surveillance game Cops and robber games Prefetching Online strategy Competitive ratio Cost of connectivity

Author: Frédéric Giroire - Ioannis Lamprou - Dorian Mazauric - Nicolas Nisse - Stéphane Pérennes - Ronan Soares -



Related documents