Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs

Ashish Goel, Michael Kapralov, Sanjeev Khanna

In this paper we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first non-trivial algorithm, with running time $O(mn)$…