Near-linear query complexity for graph inference

How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? Let G = (V, E) be a connected, undirected, and unweighted graph of bounded degree. The edge set E is initially unknown, and the graph can be accessed using a distance oracle, which receives a pair of vertices (u, v) and returns the distance between u and v. In the verification problem, we are given a hypothetical graph Ĝ = (V, Ê) and want to check whether G is equal to Ĝ. We analyze a natural greedy algorithm and prove that it uses n1+o(1) distance queries. In the more difficult reconstruction problem, Ĝ is not given, and the goal is to find the graph G. If the graph can be accessed using a shortest path oracle, which returns not just the distance but an actual shortest path between u and v, we show that extending the idea of greedy gives a reconstruction algorithm that uses n^1+o(1) shortest path queries. When the graph has bounded treewidth, we further bound the query complexity of the greedy algorithms for both problems by Õ(n). When the graph is chordal, we provide a randomized algorithm for reconstruction using Õ (n) distance queries.