Bipartite Perfect Matching is in quasi-NC

by Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

Update (April 2017): The result was extended to general graphs by Ola Svensson and Jakub Tarnawski (see ECCC TR17-059).

Oded's comments

Indeed, a great result: The abstract talks for itself. The following rough overview of the proof is indebted to a lecture by Amir Shpilka.

The core of this work is a de-randomization of the isolation lemma. Specifically, they construct a set of quasi-polynomially many weight functions, where each weight function assigns weights in a quasi-polynomial range to all possible edges of $n$-vertex bipartite graphs such that for each such graph there exists a weight functions under which there is a unique perfect matching having minimum weight.

The construction proceeds in logarithmically many rounds such that at each round a new weight functions are used to "break equalities" between a certain set of possible perfect matching (PM), while a certain potential function (which ranges in $[n]$) is cut by half. These log-many weights will be combined in a natural manner to a single weight such that equality and inequalties among sequences is reflected in the result (e.g., the sequence $(e_1,...,e_\ell)\in[B]^\ell$ is mapped to $1+\sum_{i\in[\ell]} (e_i -1)\cdot B^{i-1} \in[B^\ell]$).

The analysis is conducted with reference to a generic $n$-vertex graph, and it refers to the "alternating" weights assigned to (simple) cycles in the graph, where the weight of the cycle is the absolute value of the "signed weights" assigned to its edges such that the sign alternates when one goes around the cycle. This corresponds to the subtracting the weights of two PMs in the graph, since the symmetric difference between such PMs corresponds to a collection of cycles in which the edges alternate between this pair of PMs. The key observations are that a pairs of PMs of different weights correspond to a collection of cycles in which some cycle has non-zero weight, whereas a pair of PMs having the same *minimal* weight corresponds to a collection of cycles that have each zero weight. Hence, the goal is to select weights such that all cycles of a certain type (specifically, all cycles that correspond to pairs of PMs of minimum weight) have weight zero. This will be done in iterations.

In the first iteration, we consider the original graph, denoted $G_0$, and the set of cycles of length $L=O(\log n)$. Since the number of possible cycles is quasipolynomial (qp), one can construct a set of qp-many weights (each ranging in [pq]) that contains a weight function, called good, under which no cycle has zero weight. (Indeed, in the first iteration identifying a good weight function is easy, and can be oblivious of the input graph...) For each of these weight functions, we consider the union of all PMs of minimal weight, which yields a new graph, denoted $G_1$, that has girth greater than $L$ if the weight function is good. (Warning: the fact that the original cycles were eliminated does not mean that others cannot be formed, but the latter fact can be shown by relying on the minimal weight of the PMs.) Hence, a good weight function yields a graph (i.e., the above $G_1$) in which at least half of the vertices have degree at most two. In subsequent iterations we shall refer to length of cycles when discounting any vertex of degree two (i.e., counting only the number of vertices of degree greater than two that reside on the cycle). Indeed, the analysis of subsequent iterations branches to qp branches that correspond to the possible weight functions used in the first iteration, whereas each will have its own graph $G_1$, and will will refer to cycles of length at most $L$ (when discarding degree-2 vertices) in $G_1$.

The point is that one of the branches that enters iteration $i+1$ will correspond to a sequence of graphs $G_1,...,G_i$ in which each graph $G_j$ has girth at least $L$ (w.r.t edges of $G_{j-1}$), and so the $i+1$st iteration will yield a weight function that eliminates all cycles of length at most $L$ yielding girth greater than $L$ wrt $G_i$. In each iterations we need to handle less than $n^L$ different cycles (in fact, iteration $i+1$ the bound is $(n/2^i)^L$), but the number of vertices of degree greater than two in $G_i$ is at most $n/2^i$, and so we are done after $\log n$ iterations when all such vertices are eliminated...

The original abstract

We show that the bipartite perfect matching problem is in quasi-NC2. That is, it has uniform circuits of quasi-polynomial size and $O(log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.

See ECCC TR15-177.

Back to list of Oded's choices.