Shotgun assembly of random graphs

In the graph shotgun assembly problem, we are given the balls of radius r around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the Erdős-Rényi random graph G(n,p) G ( n , p ) for a wide range of values of r . We determine the threshold for reconstructibility for each r≥ 3 r ≥ 3 , extending and improving substantially on results of Mossel and Ross for $$r=3$$ r = 3 . For $$r=2$$ r = 2 , we give upper and lower bounds that improve on results of Gaudio and Mossel by polynomial factors. We also give a sharpening of a result of Huang and Tikhomirov for $$r=1$$ r = 1 .