{"id":"arxiv/2610.16675","url":"https://arxiv.org/abs/2610.16675","tags":["math.PR","cs.DS","math.ST"],"score":0,"title":"Graph Matching in Random Geometric Graphs I: Efficient Algorithms","domain":"math.PR","source":"arxiv","authors":["Dong Huang","Ankang Jiao","Shuangping Li","Zhangsong Li"],"reviews":0,"subject":"math.PR","summary":"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$,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}