The Algorithmic Phase Transition of Random Graph Alignment Problem

arXiv2307.06590MaRDI QIDQ6443585FDOQ6443585

Authors: Hang Du, Shuyang Gong, Rundong Huang 

Publication date: 13 July 2023

Abstract: We study the graph alignment problem over two independent ErdH{o}s-R'enyi graphs on $n$ vertices, with edge density $p$ falling into two regimes separated by the critical window around $p_c=sqrtlogn/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 $sqrt8/9$ multiplicative constant factor gap between achievable and optimal solutions.

This page was built for publication: The Algorithmic Phase Transition of Random Graph Alignment Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6443585)