The Algorithmic Phase Transition of Random Graph Alignment Problem

07/13/2023

∙

by   Hang Du, et al.

∙

0

∙

share

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 around p_c=√(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.