A Deterministic Parallel Algorithm
for Bipartite Perfect Matching
By Stephen Fenner, Rohit Gurjar, and Thomas Thierauf
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
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.
A perfect matching in a graph is a subset of edges such that
every vertex has exactly one edge incident on it from the
subset (Figure 1). The perfect matching problem, PM, asks
whether a given graph contains a perfect matching. The
problem has played an important role in the study of algorithms and complexity. The first polynomial-time algorithm
for the problem was given by Edmonds,
7 which, in fact,
motivated him to propose polynomial time as a measure of
Perfect matching was also one of the first problems to be
studied from the perspective of parallel algorithms. A par-
allel algorithm is one where we allow use of polynomially
many processors running in parallel. And to consider a par-
allel algorithm as efficient, we require the running time to
be much smaller than a polynomial. In particular, the com-
plexity class NC is defined as the set of problems which can
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.
be solved by a parallel computer with polynomially many
processors in poly-logarithmic time.
Lovász19 gave an efficient randomized parallel algorithm
for the matching problem, putting it in the complexity class
RNC (randomized NC). The essence of his parallel algorithm
was a randomized reduction from the matching problem to
a determinant computation. A determinant computation in
turn reduces to matrix multiplication (see4), which is well
known to have efficient parallel algorithms.
One of the central themes in the theory of computation is
to understand the power of randomness, that is, whether all
problems with an efficient randomized algorithm also have
a deterministic one. The matching problem has been widely
studied under this theme. It has been a long-standing open
question whether randomness is necessary for a parallel
matching algorithm, that is, whether the problem is in NC.
One can also ask for a parallel algorithm to construct a
perfect matching in the graph if one exists (Search-PM). Note
that there is a standard search-to-decision reduction for the
matching problem, but it does not work in parallel. Karp,
Upfal, and Wigderson18 and later, Mulmuley, Vazirani, and
Vazirani21 gave RNC algorithms for Search-PM. The latter
work introduced the celebrated Isolation Lemma and used
it to solve Search-PM in RNC. They assign some weights to
the edges of the graph, call a weight assignment isolating
for a graph G if there is a unique minimum weight perfect
matching in G. Here, the weight of a perfect matching is simply the sum of the weights of the edges in it. Given an isolating weight assignment with polynomially bounded integer
weights, they can find the minimum weight perfect matching in G in NC (again via determinant computations).
Note that if we allow exponentially large weights then it
is trivial to construct an isolating weight assignment: assign
weight 2i to the ith edge for 1 ≤ i ≤ m, where m is the number
of edges. This, in fact, ensures a different weight for each perfect matching. The challenge, however, is to find an isolating weight assignment with polynomially bounded weights.
This is where the Isolation Lemma comes in: it states that if
each edge is assigned a random weight from a polynomially
bounded range then such a weight assignment is isolating
with high probability.
Note that since there can be exponentially many perfect
matchings in a graph, there will definitely be many collisions under a polynomially bounded weight assignment,
that is, many perfect matchings will get the same weight.
Figure 1. A graph, with the bold edges showing a perfect matching.
*Supported by DFG grant TH 472/4.