Matching randomly in parallel

Abstract: "In this paper, the parallel complexity of the Random Matching Problem-a problem of generating a perfect matching in a bipartite graph uniformly in random-is considered. We show that the only known polynomial time random matching algorithm, due to Broder, Jerrum, and Sinclair, can not be parallelized in NC, unless NC = P. The reduction is from the Lexical First Maximal Independent Set Problem. This result shows many interesting structural properties between matching and lexical first maximal independent sets. It also leaves many interesting and important open questions. We also show that any polynomial time scheme (NC scheme) for the Random Maximal Independent Set Problem implies NP = RP (NP = RNC). This provides another example that the problem of uniform random generation is harder than the corresponding construction problem.