Graph reconstruction and verification

How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? We assume that the unknown graph G is connected, unweighted, and has bounded degree. In the reconstruction problem, the goal is to find the graph G. In the verification problem, we are given a hypothetical graph Ĝ and want to check whether G is equal to Ĝ. We provide a randomized algorithm for reconstruction using O (n3/2) distance queries, based on Voronoi cell decomposition. Next, we analyze natural greedy algorithms for reconstruction using a shortest path oracle and also for verification using either oracle, and showthat their query complexity is n1+o(1).We further improve the query complexitywhen the graph is chordal or outerplanar. Finally,we showsome lower bounds, and consider an approximate version of the reconstruction problem.