Shotgun Assembly of Erdos-Renyi Random Graphs

Abstract

Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of \ER random graphs $G(n,p_n)$, where $p_n=n^{-\alpha }$ for $0<\alpha <1$. We consider both reconstruction up to isomorphism as well as exact reconstruction (recovering the vertex labels as well as the structure). We show that given the collection of distance-$1$ neighborhoods, $G$ is exactly reconstructable for $0<\alpha <\frac{1}{3}$, but not reconstructable for $\frac{1}{2}<\alpha <1$. Given the collection of distance-$2$ neighborhoods, $G$ is exactly reconstructable for $\alpha \in \left(0,\frac{1}{2}\right)\cup \left(\frac{1}{2},\frac{3}{5}\right)$, but not reconstructable for $\frac{3}{4}<\alpha <1$.

13 pages