# A polynomial-time approximation scheme for the maximal overlap of two independent ErdHos-R'enyi graphs

arXiv: https://arxiv.org/abs/2210.07823 · HTML: https://mlsanity.com/paper/2210.07823/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2022.

## Built on by (most cited first, 3 of 3)

- [A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation](https://mlsanity.com/paper/2306.00266/) (2023)
- [A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation](https://mlsanity.com/paper/2212.13677/) (2022)
- [Efficiently matching random inhomogeneous graphs via degree profiles](https://mlsanity.com/paper/2310.10441/) (2023)

## Abstract (arXiv)

For two independent ErdHos-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 fracn2α-1 for p=n-α with some constant α∈ (1/2,1).