Graph Reconstruction from Noisy Random Subgraphs

We consider the problem of reconstructing an undirected graph G on n vertices given multiple random noisy subgraphs or "traces". Specifically, a trace is generated by sampling each vertex with probability pᵥ, then taking the resulting induced subgraph on the sampled vertices, and then adding noise in the form of either (a) deleting each edge in the subgraph with probability 1-pₑ, or (b) deleting each edge with probability fₑ and transforming a non-edge into an edge with probability fₑ. We show that, under mild assumptions on pᵥ, pₑ and fₑ, if G is selected uniformly at random, then O (pₑ^-1 pᵥ^-2 n) or O ( (fₑ-1/2) ^-2 pᵥ^-2 n) traces suffice to reconstruct G with high probability. In contrast, if G is arbitrary, then ( (n) ) traces are necessary even when pᵥ=1, pₑ=1/2.