Economical Graph Discovery

We consider the problem of graph discovery in settings where the graph topology is known and the edge weights are hidden. The setting consists of a weighted graph G with n vertices and m edges and with designated source s and destination t . We study two different discovery problems, namely, (i) edge weight discovery, where the goal is to discover all edge weights, and (ii) shortest path discovery, where the goal is to discover a shortest ( s , t )-path. This discovery is done by means of agents that traverse different ( s , t )-paths in multiple rounds and report back the total cost they incurred. Three cost models are considered, differing from each other in their approach to congestion effects. In particular, we consider congestion-free models as well as models with positive and negative congestion effects. We seek bounds on the number of rounds and the number of agents required to complete the edge weights or the shortest path discovery. Several results concerning such bounds for both directed and undirected graphs are established. Among these results, we show that (1) for undirected graphs, all edge weights can be discovered within a single round consisting of m agents, (2) discovering a shortest path in either undirected or directed acyclic graphs requires at least m − n + 1 agents, and (3) the edge weights in a directed acyclic graph can be discovered in m rounds with m + n − 2 agents under congestion-aware cost models. Our study introduces a new setting of graph discovery under uncertainty and provides fundamental understanding of the problem.