Stochastic Graph Exploration

Exploring large-scale 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. Adaptive strategies are dynamically updated to adjust to the current status of the exploration process. Nonadaptive oblivious strategies are also appealing since they greatly reduce the computation and communication costs required by adaptive strategies. In order to model this process we introduce the \emph{stochastic graph exploration problem}. The input is an undirected graph $G=(V,E)$ with a source vertex $s$, stochastic edge costs for the edges 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 has maximum 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 with small adaptivity gap that are competitive against the optimal adaptive strategy. Unfortunately, we prove an $\Omega(n)$ adaptivity gap for the stochastic graph exploration problem even on a tree of $n$ vertices that compares against the $O(1)$ adaptivity gap of the stochastic knapsack problem. We circumvent this negative result by showing that $O(\log nR)$ resource augmentation suffices for an adaptivity gap $O(1)$ on trees and $O(\log nR)$ on general graphs. In order to achieve this result, we reduce stochastic graph exploration to a memoryless process -- the {\em minesweeper} problem, -- which assigns to every edge that is traversed a probability that the process would terminate. For this problem, interesting in its own, we present an optimal polynomial time algorithm on trees and a $O(\log nR)$ approximation for general graphs. We also study the problem in which the maximum cost of an edge is a logarithmic fraction of the budget. We show under this condition the existence of polynomial time oblivious strategies that use $1+\epsilon$ budget to obtain adaptivity gaps $1+\epsilon$ on trees and $8+\epsilon$ for general graphs. Finally, we provide additional results on the structure and the complexity of nonadaptive and adaptive strategies.

• Algorithms and Theory