2026-07-25T01:58:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24498 2025-12-16T14:00:00Z ddc:004 open_access

Reconstructing Random Graphs from Distance Queries Krivelevich, Michael Zhukovskii, Maksim random graphs graph reconstruction distance queries query complexity 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-d}p^{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-d}p^{2-d}ln n) distance queries with high probability, and this is best possible. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Krivelevich and Maksim Zhukovskii 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.30 urn:nbn:de:0030-drops-244982 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.30 eng https://creativecommons.org/licenses/by/4.0/legalcode