Distance Reconstruction of Sparse Random Graphs

In the distance query model, we are given access to the vertex set of a $n$-vertex graph $G$, and an oracle that takes as input two vertices and returns the distance between these two vertices in $G$. We study how many queries are needed to reconstruct the edge set of $G$ when $G$ is sampled according to the $G(n,p)$ Erdős-Renyi-Gilbert distribution. Our approach applies to a large spectrum of values for $p$ starting slightly above the connectivity threshold: $p\ge \frac{2000\log n}{n}$. We show that there exists an algorithm that reconstructs $G\sim G(n,p)$ using $O({\mathrm{\Delta }}^{2}n\log n)$ queries in expectation, where $\mathrm{\Delta }$ is the expected average degree of $G$. In particular, for $p\in [\frac{2000\log n}{n},\frac{{\log }^{2}n}{n}]$ the algorithm uses $O(n{\log }^{5}n)$ queries.