The planted matching problem: Phase transitions and exact results

We study the problem of recovering a planted matching in randomly weighted complete bipartite graphs Kn,n. For some unknown perfect matching M∗, the weight of an edge is drawn from one distribution P if e∈M∗ and another distribution Q if e∉M∗. Our goal is to infer M∗, exactly or approximately, from the edge weights. In this paper we take P=exp(λ) and Q=exp(1/n), in which case the maximum-likelihood estimator of M∗ is the minimum-weight matching...