  We study the graph alignment problem over two independent Erd\H{o}s-R\'enyi
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$ lies in the dense regime, resulting in a $\sqrt{8/9}$
multiplicative constant factor gap between achievable and optimal solutions.
