Matching is as easy as matrix inversion
Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani · 1987
A new algorithm for finding a maximum matching in a general graph is presented; its special feature being that the only computationally non-trivial step required in its execution is the inversion of a single integer matrix.Since this step can be parallelized, we get a simple parallel (RNC2) algorithm.At the heart of our algorithm lies a probabilistic lemma, the isolating lemma.We show applications of this lemma to parallel computation and randomized reductions.