The Algorithmic Phase Transition of Random Graph Alignment Problem

Hang Du, Shuyang Gong, Rundong Huang

We study the graph alignment problem over two independent Erdős-Rényi graphs on $n$ vertices, with edge density $p$ falling into two regimes separated by the critical window arou…