We study the graph alignment problem over two independent Erdős–Rényi random graphs on n vertices, with edge density p falling into two regimes separated by the critical window around \(p_c:=\sqrt{\log n/n}\) . Our result reveals an algorithmic phase transition for this random optimization problem: polynomial-time approximation schemes exist in the sparse regime, while statistical-computational gap emerges in the dense regime. Additionally, we establish a sharp transition on the performance of online algorithms for this problem when p is in the dense regime, resulting in a \(\sqrt{8/9}\) multiplicative constant factor gap between achievable solutions and optimal solutions.
