A Caltech Library Service

A Deterministic Parallel Algorithm for Bipartite Perfect Matching

Fenner, Stephen and Gurjar, Rohit and Thierauf, Thomas (2019) A Deterministic Parallel Algorithm for Bipartite Perfect Matching. Communications of the ACM, 62 (3). pp. 109-115. ISSN 0001-0782.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


A fundamental quest in the theory of computing is to understand the power of randomness. It is not known whether every problem with an efficient randomized algorithm also has one that does not use randomness. One of the extensively studied problems under this theme is that of perfect matching. The perfect matching problem has a randomized parallel (NC) algorithm based on the Isolation Lemma of Mulmuley, Vazirani, and Vazirani. It is a long-standing open question whether this algorithm can be derandomized. In this article, we give an almost complete derandomization of the Isolation Lemma for perfect matchings in bipartite graphs. This gives us a deterministic parallel (quasi-NC) algorithm for the bipartite perfect matching problem. Derandomization of the Isolation Lemma means that we deterministically construct a weight assignment so that the minimum weight perfect matching is unique. We present three different ways of doing this construction with a common main idea.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemConference Paper
Additional Information:© 2019 ACM, Inc. We would like to thank Manindra Agrawal and Nitin Saxena for their constant encouragement and very helpful discussions. We thank Arpita Korwar for discussions on some other techniques used in this research, Jacobo Torán for discussions on the number of shortest cycles, and Nisheeth Vishnoi for helpful comments. Supported by DFG grant TH 472/4. The original version of this paper is entitled "Bipartite Perfect Matching is in quasi-NC" and was published in the Proceedings of the 48th ACM Symposium on the Theory of Computing (STOC), 2016.
Funding AgencyGrant Number
Deutsche Forschungsgemeinschaft (DFG)TH 472/4
Issue or Number:3
Record Number:CaltechAUTHORS:20190222-080917724
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93176
Deposited By: Tony Diaz
Deposited On:22 Feb 2019 17:04
Last Modified:03 Oct 2019 20:51

Repository Staff Only: item control page