Reconstructing random graphs from distance queries

2024/04/28 by Krivelevich, Michael, Zhukovskii, Maksim · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2404.18318

Abstract

We estimate the minimum number of distance queries that is sufficient to reconstruct the binomial random graph G(n,p) with constant diameter with high probability. We get a tight (up to a constant factor) answer for all p>n^-1+o(1) outside "threshold windows" around n^{-k/(k+1)+o(1)}, k∈ℤ_>0: with high probability the query complexity equals Θ(n^4-dp^2-d), where d is the diameter of the random graph. This demonstrates the following non-monotone behaviour: the query complexity jumps down at moments when the diameter gets larger; yet, between these moments the query complexity grows. We also show that there exists a non-adaptive algorithm that reconstructs the random graph with O(n^4-dp^2-dln n) distance queries with high probability, and this is best possible.

Cited by

• Exact Learning of Weighted Graphs Using Composite Queries
• Finding the diameter of a tree with distance queries
• Complexity of learning matchings and half graphs via edge queries

Related

• Distance Reconstruction of Sparse Random Graphs
• Graph Reconstruction via Distance Oracles
• Reconstruction of geometric random graphs with the Simple algorithm
• Finding paths in sparse random graphs requires many queries
• Optimal distance query reconstruction for graphs without long induced cycles