Graph Matching in Random Geometric Graphs I: Efficient Algorithms
We study the recovery of the hidden vertex correspondence between two correlated dense random geometric graphs. Each graph is generated from $n$ latent unit vectors in $\mathbb R^d$; the vectors $u_i^A$ and $u_i^B$ of corresponding vertices satisfy $\langle u_i^A,u_i^B\rangle=ρ$, and the vertex labels of the second graph are permuted by an unknown permutation $π$. For every fixed correlation $ρ\in(0,1]$ and every edge density bounded away from zero and one, we give a randomized polynomial time algorithm that recovers $π$ exactly with probability tending to one whenever $d\ge(\log n)^L$,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.16675
curl -X POST /api/v1/records/arxiv/2610.16675/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.16675/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'