论文标题
两个独立Erdős-rényi图的最大重叠的多项式时间近似方案
A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
论文作者
论文摘要
对于两个独立的erdős-rényi图$ \ mathbf g（n，p）$，我们研究了所有可能的顶点对应关系上这两个图的最大重叠（即，共同边的数量）。我们提出了一种多项式时间算法，该算法找到一个顶点对应关系，其重叠近似于最大的重叠至任意接近1的乘法因子，作为副产品，我们证明了最大重叠是$ \ frac {n} $ plac {n} $ p for $ p for $ p = n} $ p. （1/2,1）$。
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α-1}$ for $p=n^{-α}$ with some constant $α\in (1/2,1)$.
