Computing shortest paths with uncertainty

We consider the problem of estimating the length of the shortest path from a vertex s to a vertex t in a DAG whose edge lengths are known only approximately but can be determined exactly at a cost. Initially, for each edge e, the length of e is known only to lie within an interval [le,he]; the estimation algorithm can pay we to find the exact length of e. We study the problem of finding the cheapest set of edges such that, if exactly these edges are queried, the length of the shortest s–t path will be known, within an additive κ⩾0, an input parameter. An actual s–t path, whose true length exceeds that of the shortest s–t path by at most κ, will be obtained as well. The problem of finding a cheap set of edge queries is in neither NP nor co-NP unless NP = co-NP. We give positive and negative results for two special cases and for the general case, which we show is in Σ2.