The algorithmic phase transition of random graph alignment problem
成果类型：
Article
署名作者：
Du, Hang; Gong, Shuyang; Huang, Rundong
署名单位：
Massachusetts Institute of Technology (MIT); Peking University
刊物名称：
PROBABILITY THEORY AND RELATED FIELDS
ISSN/ISSBN：
0178-8051
DOI：
10.1007/s00440-025-01370-z
发表日期：
2025
页码：
1233-1288
关键词：
摘要：
We study the graph alignment problem over two independent Erdos-R & eacute;nyi random graphs on n vertices, with edge density p falling into two regimes separated by the critical window around p(c ):= root 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 root 8/9 multiplicative constant factor gap between achievable solutions and optimal solutions.
来源URL：