Before revision:  For instance, when p is a constant or p=n^{-3/4}, we show that only \Omega(\sqrt{n\log n}) correct seeds suffice for perfect matching, while the previously best-known results demand \Omega(n) and \Omega(n^{3/4}\log n) correct seeds, respectively} . Numerical experiments on both synthetic and real graphs corroborate our theoretical findings and show that our 2-hop algorithm significantly outperforms the 1-hop algorithm when the graphsare relatively sparse .
After revision:  For instance, when p is a constant or p=n^{-3/4}, we show that only \Omega(\sqrt{n\log n}) correct seeds suffice for perfect matching, while the previously best-known results demand \Omega(n) and \Omega(n^{3/4}\log n) correct seeds, respectively} . Numerical experiments on both synthetic and real graphs corroborate our theoretical findings and show that our 2-hop algorithm on a variety of synthetic and real graphs .