Graph Reconstruction and Verification
Sampath Kannan, Claire Mathieu, Hang Zhou · ACM Transactions on Algorithms · 2018
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 Õ( n 3/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 show that their query complexity is n 1+ o (1) . We further improve the query complexity when the graph is chordal or outerplanar. Finally, we show some lower bounds, and consider an approximate version of the reconstruction problem.