The Algorithmic Phase Transition of Random Graph Alignment Problem

2023/07/13 by Hang Du, Shuyang Gong, Du, Hang +3 · 5 citations
Computer Science · #Optimization and Search Problems #Complexity and Algorithms in Graphs #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2307.06590

Abstract

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.

Cited by

• Testing Correlation in Graphs by Counting Bounded Degree Motifs
• Sharp Online Hardness for Large Balanced Independent Sets
• Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
• Strong Low Degree Hardness for the Number Partitioning Problem

Related

• Computational thresholds in high-dimensional statistics: the case of graph alignment
• The feasibility of multi-graph alignment: a Bayesian approach
• The graph alignment problem: fundamental limits and efficient algorithms
• Graph alignment in sparse inhomogeneous models via self-overlap
• Random Graph Matching with Improved Noise Robustness