Abstract

Consider two copies of the same $G(n,p)$ graph and erase independently the edges of each copy with probability $t < p$. This procedure creates two correlated random graphs. We discuss a randomized algorithm recovering the matching between the vertices of the two graphs for a certain range of parameters.