A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs

Abstract

For two independent Erdős-Rényi 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)$.

38 pages, 3 figures