  For two independent Erd\H{o}s-R\'enyi graphs $\mathbf G(n,p)$, we study the
maximal overlap (i.e., the number of common edges) of these two graphs over all
possible vertex correspondence. We present a polynomial-time algorithm which
finds a vertex correspondence whose overlap approximates the maximal overlap up
to a multiplicative factor that is arbitrarily close to 1. As a by-product, we
prove that the maximal overlap is asymptotically $\frac{n}{2\alpha-1}$ for
$p=n^{-\alpha}$ with some constant $\alpha\in (1/2,1)$.
