Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing
cs.DS, math.ST, stat.ML, stat.TH
Submitted: 2026-11-01
Updated: 2026-11-01
Comments: 67 pages, 3 figures
License: http://creativecommons.org/licenses/by/4.0/
The gist: This paper presents a near-quadratic-time algorithm that correctly matches almost all nodes of two correlated Erdős-Rényi graphs without any incorrect matches.
Abstract
This paper presents a near-quadratic-time algorithm that correctly matches almost all nodes of two correlated Erdős-Rényi graphs without any incorrect matches. Each graph has average degree λ and its edges are subsampled from a common parent Erdős-Rényi graph with n nodes, with subsampling probability s. The nodes of one graph are then relabeled by an unknown permutation. The algorithm is built on a test for correlated versus independent Galton-Watson trees with approximated likelihood ratios. For every constant s> sqrt C Otter, where C Otter about0.338 is Otter's tree-counting constant, and every λ=ω(1) with λ=(n) O(1), the algorithm outputs a partial matching of size n-o(n) that contains no incorrect matches with high probability. If, in addition, λs at least(1+ε) n for a constant ε>0, a seeded completion step recovers the permutation exactly. In both cases, the time complexity of the algorithm is n 2+o(1) with high probability, whereas previous polynomial-time algorithms with the same guarantees either have a time-complexity bound whose exponent goes to infinity as s approaches sqrt C Otter from above, or apply only when s is close to 1.
Sources
- Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests
- Exact alignment recovery for correlated Erd\H{o}s-R'enyi graphs
- A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time