Stephen Fenner, Rohit Gurjar, Thomas Thierauf
Abstract:
The perfect matching problem has a randomized NC-algorithm based on the Isolation Lemma
of Mulmuley, Vazirani and Vazirani.
We give an almost complete derandomization of the Isolation Lemma
for perfect matchings in bipartite graphs.
This gives us a deterministic Quasi-NC-algorithm for the bipartite perfect matching problem.
The outline presented here emphasizes a geometric point of view.
We think that this will be useful also for the perfect matching problem in general graphs.