Graph Reconstruction from Noisy Random Subgraphs

Andrew McGregor, Rik Sengupta

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…