Theorem 1. 2. For bipartite graphs, PM and Search-PM are in
quasi-NC2.
1. 1. The isolation technique
At the heart of our isolation approach is a cycle elimination
technique. It is easy to see that if we take a union of two perfect matchings, we get a set of disjoint cycles and singleton
edges (see Figure 2). Each of these cycles has even length
and has edges alternating from the two perfect matchings.
Cycles thus play an important role in isolating a perfect
matching. Given a weight assignment on the edges, let us
define the circulation of an even cycle C to be the difference
of weights between the set of odd-numbered edges and the
set of even-numbered edges in cyclic order around C. Clearly,
if all the cycles in the union of two perfect matchings have
zero circulations, then the two perfect matchings will have
the same weight. It turns out that the converse is also true
when the two perfect matchings under consideration are of
the minimum weight.
6 This observation is the starting point
of our cycle elimination technique.
In the case of bipartite graphs, this observation can be
further generalized. We show that for any weight assignment w on the edges of a bipartite graph, if we consider the
union of all the minimum weight perfect matchings, then
it has only those cycles which have zero circulation (Lemma
2. 1). This means that if we design the weights w such that a
particular cycle C has a nonzero circulation, then C does not
appear in the union of minimum weight perfect matchings,
that is, at least one of the edges in C does not participate in
any minimum weight perfect matchings. This is the way we
will be eliminating cycles.
If we eliminate all cycles this way, we will get a unique minimum weight perfect matching, for if there were two minimum
weight perfect matchings, their union would contain a cycle.
However, it turns out that there are too many cycles in the
graph, and it is not possible to ensure nonzero circulations
simultaneously for all cycles while keeping the edge weights
small (proved in17). Instead, what is achievable is nonzero
circulation for any polynomially large set of cycles using well-known hashing techniques. In short, we can eliminate any
desired set of a small number of cycles at once. With this tool
in hand we would like to eliminate all cycles—whose number
can be exponentially large—in a small number of rounds.
We present three different ways of achieving this. The first
two of these have appeared before in different versions of
our article.
10 The third has not appeared anywhere before.
The beauty of the Isolation Lemma is that for the minimum
weight, there will be a unique perfect matching with high
probability.
Lemma 1. 1 (Isolation Lemma Mulmuley, Vazirani, and
Vazirani21). Let G(V, E) be a graph, |E| = m, and w ∈ { 1, 2, . . .,
km}E be a uniformly random weight assignment on its edges,
for some k ≥ 2. Then w is isolating with probability at least
1 − 1/k.
Proof. Let e be an edge in the graph. We first give an upper
bound on the probability that there are two minimum-weight perfect matchings, one containing e and other not
containing e. For this, say the weight of every other edge
except e has been fixed. Let W be the minimum weight of any
perfect matching that avoids e, and let W′ + w(e) be the minimum weight of any perfect matching that contains e.
Now, what is the probability that these two minimum
weights are equal? Since W and W′ are already fixed by the
other edges, and w(e) is chosen uniformly and randomly
between 1 and km,
By the union bound,
Now, to finish the proof, observe that there is a unique
minimum weight perfect matching if and only if there is no
such edge with the above property.
One way to obtain a deterministic parallel (NC) algorithm
for the perfect matching problem is to derandomize this
lemma. That is, to deterministically construct such a polynomially bounded isolating weight assignment in NC. This has
remained a challenging open question.
Derandomization of the Isolation Lemma has been
known for some special classes of graphs, for example, planar bipartite graphs,
6, 26 strongly chordal graphs,
5 and graphs
with a small number of perfect matchings.
1, 14 Here, we present an almost complete derandomization of the Isolation
Lemma for bipartite graphs. The class of bipartite graphs
appears very naturally in the study of perfect matchings. A
graph is bipartite if there is a partition of its vertex set into
two parts such that each edge connects a vertex from one
part to a vertex from the other (the graph in Figure 1 is bipartite). Thus, a perfect matching in a bipartite graph matches
every vertex in one part to exactly one vertex in the other.
In Section 3, we construct an isolating weight assignment
for bipartite graphs with quasi-polynomially large (nO(log n))
weights, where n is the number of vertices in the graph. Note
that this is slightly worse than what we would have ideally
liked, which is—polynomially bounded weights. Hence, we
do not get an NC algorithm. Instead, we get that for bipartite
graphs, the problems PM and Search-PM are in quasi-NC2.
That is, the problems can be solved in O(log2 n) time using
nO(log n) parallel processors. A more detailed exposition is in
the conference version of the article.
10
Figure 2. Two perfect matchings, with red and blue edges,
respectively. Their union forms a set of disjoint cycles and edges.