Stochastic Graph Exploration

We introduce the stochastic graph exploration problem. The input is an undirected graph G with a source vertex s, stochastic edge costs, and deterministic rewards of vertices. The goal is to find a set F of edges of total cost at most 1, such that the subgraph of G induced by F is connected, contains s, and has maximum total reward. The set F is constructed by adding edges one by one and after each step the subgraph of G induced by F has to be connected and contain s. When an edge is chosen, its actual cost is revealed. The chosen edge has to be added to F, unless the total cost of edges in F would exceed 1, in which case the process finishes.

We show that this problem generalizes the stochastic knapsack problem. However, as opposed to knapsack problem, the adaptivity gap of the stochastic graph exploration problem is superconstant. On the positive side, we show bi-criteria approximation algorithms both for trees and general graphs.