2024/07/24 by Bastide, Paul · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2407.17376
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 ≥ (2000 log n)/(n). We show that there exists an algorithm that reconstructs G ∼ G(n,p) using O( Δ2 n log n ) queries in expectation, where Δ is the expected average degree of G. In particular, for p ∈ [(2000 log n)/(n), (log2 n)/(n)] the algorithm uses O(n log5 n) queries.