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.