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 Pv, 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-pe, or b) deleting each edge with probability fe and transforming a non-edge into an edge with probability fe. We show that, under mild assumptions on pv, pe and fe, if G is selected uniformly at random, then O(pe-1pv-2logn) or O((fe-1/2) -2pv-2logn) traces suffice to reconstruct G with high probability. In contrast, if G is arbitrary, then exp (Ω (n)) traces are necessary even when pv = 1, Pe = 1/2.