Abstract
Exploring largescale networks is a time consuming and expensive task which is usually operated in a complex and uncertain environment. A crucial aspect of network exploration is the development of suitable strategies that decide which nodes and edges to probe at each stage of the process.
To model this process, we introduce the stochastic graph exploration problem. The input is an undirected graph G=(V,E) with a source vertex s, stochastic edge costs drawn from a distribution pi_e, e in E, and rewards on vertices of maximum value R. The goal is to find a set F of edges of total cost at most B such that the subgraph of G induced by F is connected, contains s, and maximizes the total reward. This problem generalizes the stochastic knapsack problem and other stochastic probing problems recently studied.
Our focus is on the development of efficient nonadaptive strategies that are competitive against the optimal adaptive strategy. A major challenge is the fact that the problem has an Omega(n) adaptivity gap even on a tree of n vertices. This is in sharp contrast with O(1) adaptivity gap of the stochastic knapsack problem, which is a special case of our problem. We circumvent this negative result by showing that O(log nR) resource augmentation suffices to obtain O(1) approximation on trees and O(log nR) approximation on general graphs. To achieve this result, we reduce stochastic graph exploration to a memoryless process  the minesweeper problem  which assigns to every edge a probability that the process terminates when the edge is probed. For this problem, interesting in its own, we present an optimal polynomial time algorithm on trees and an O(log nR) approximation for general graphs.
We study also the problem in which the maximum cost of an edge is a logarithmic fraction of the budget. We show that under this condition, there exist polynomialtime oblivious strategies that use 1+epsilon budget, whose adaptivity gaps on trees and general graphs are 1+epsilon and 8+epsilon, respectively. Finally, we provide additional results on the structure and the complexity of nonadaptive and adaptive strategies.
BibTeX  Entry
@InProceedings{anagnostopoulos_et_al:LIPIcs:2019:10712,
author = {Aris Anagnostopoulos and Ilan R. Cohen and Stefano Leonardi and Jakub Lacki},
title = {{Stochastic Graph Exploration}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {136:1136:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10712},
URN = {urn:nbn:de:0030drops107122},
doi = {10.4230/LIPIcs.ICALP.2019.136},
annote = {Keywords: stochastic optimization, graph exploration, approximation algorithms}
}
Keywords: 

stochastic optimization, graph exploration, approximation algorithms 
Collection: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) 
Issue Date: 

2019 
Date of publication: 

04.07.2019 