The Planted Matching Problem: Phase Transitions and Exact Results

Mehrdad Moharrami, Cristopher Moore, Jiaming Xu

We study the problem of recovering a planted matching in randomly weighted complete bipartite graphs $K_{n,n}$. For some unknown perfect matching $M^{\ast }$, the weight of an edge is dr…