Random graph matching refers to recovering the underlying vertex correspondence between two Erd\H{o}s-R\'{e}nyi graphs with correlated edges. This can be viewed as an average-case and noisy version of the graph isomorphism problem. The maximum likelihood estimator is equivalent to the intractable quadratic assignment problem. 

　　For seeded problems, where an initial seed set of correctly matched vertex pairs is revealed as side information, our result provides a dramatic improvement over previously known results. We show that it is possible to achieve the information-theoretic limit of graph sparsity in time polynomial in the number of vertices $n$. Moreover, we show the number of seeds needed for exact recovery in polynomial-time can be as low as $n^{\epsilon}$ in the sparse graph regime with the average degree smaller than $n^{\epsilon}$) and $\Omega(\log n)$ in the dense graph regime. 

　　For unseeded problems, we develop a nearly linear-time algorithm which perfectly recovers the underlying true vertex correspondence, provided that the two observed graphs differ by at most $epsilon=O(1/log^2(n) )$ fraction of edges in the sparse graph regime and $espilon=O( 1/log^{2/3}(n) )$ fraction of edges in the dense graph regime. The best-known result before this work achieves $\epsilon=O(1)$ with an $n^{O(\log n)}$-time algorithm.