The Algorithmic Phase Transition of Random Graph Alignment Problem

We study the graph alignment problem over two independent ErdHos-R'enyi graphs on n vertices, with edge density p falling into two regimes separated by the critical window around pc=√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 √8/9 multiplicative constant factor gap between achievable and optimal solutions.