A Deterministic Parallel Algorithm for Bipartite Perfect Matching
- Creators
- Fenner, Stephen
- Gurjar, Rohit
- Thierauf, Thomas
Abstract
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.
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.Additional details
- Eprint ID
- 93176
- DOI
- 10.1145/3306208
- Resolver ID
- CaltechAUTHORS:20190222-080917724
- TH 472/4
- Deutsche Forschungsgemeinschaft (DFG)
- Created
-
2019-02-22Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field