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...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on algorithms 2018-10, Vol.14 (4), p.1-30, Article 40
Main Authors: Kannan, Sampath, Mathieu, Claire, Zhou, Hang
Format: Article
Language:English
Subjects:
Computational Complexity
Computer Science
Data structures design and analysis
Design and analysis of algorithms
Graph algorithms analysis
Network algorithms
Networks
Theory of computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Õ(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 show that their query complexity is n1+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.
ISSN:1549-6325
1549-6333
DOI:10.1145/3199606