Computational Complexity: Bipartite Perfect Matching in Deterministic NC

Sunday, July 19, 2026

Bipartite Perfect Matching in Deterministic NC

Nutan Limaye and Thore Husfeldt guest post on the new deterministic parallel algorithm for bipartite perfect matching by Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj and Thomas Thierauf.

The post will try to explain three main things about the result. What is the result? Why is it important? And finally, how did the authors prove it?

We will assume that the reader is an undergraduate student in CS (i.e., the reader knows basics of discrete mathematics, linear algebra, and algorithm design).

What?

The main result can be stated in just one line! Bipartite Perfect Matching can be solved in NC. Let's now understand what each of these terms means.

Bipartite Perfect Matching. A bipartite graph has two disjoint sets of vertices, say \(L, R\), and any edge connects one vertex of \(L\) and one vertex of \(R\). A matching in a graph is a subset of edges such that no two edges have a vertex in common. A perfect matching is a matching in which each vertex of the graph appears exactly once. Let's take the following example. Here is a bipartite graph.

It has two perfect matchings. One is \(\{(v_1, w_1), (v_2, w_3), (v_3, w_2)\}\) and the other is \(\{(v_1, w_2), (v_2, w_1), (v_3, w_3)\}\).

We will assume that the graph is given as a matrix, known as the bi-adjacency matrix. The bi-adjacency matrix of a bipartite graph has \(A_{ij} = 1\) whenever \((i,j)\in E(G)\). For our running example, here is how we will receive the input:<br>\[<br>A_G =<br>\begin{bmatrix}<br>1 & 1 & 0 \\<br>1 & 0 & 1 \\<br>0 & 1 & 1<br>\end{bmatrix}\,.<br>\]<br>Now, we are ready to define the Bipartite Perfect Matching (BPM for short) problem. Given a bipartite graph as a bi-adjacency matrix, check whether there is a perfect matching in the graph or not.

NC. The next term we need to explain is NC. It is a complexity class named after Nick Pippenger, which consists of a class of problems solvable by parallel algorithms that use polynomially many processors and have parallel running time that is considerably smaller than polynomial. More specifically, the parallel running time is polylogarithmic. You can simply think of this as a class of problems that have efficient parallel algorithms.

Let us begin with a simple example. Suppose we want to multiply \(n\) numbers, \(x_1,\ldots,x_n\). One approach is to first multiply \(x_1\) and \(x_2\), then multiply the result by \(x_3\), and continue in this way until we reach \(x_n\). This is a sequential algorithm.

A parallel algorithm proceeds differently. It first pairs up the numbers and multiplies all pairs simultaneously. This produces \(n/2\) numbers, giving a new instance of the same problem with only half as many inputs. We then repeat the process: pair up the remaining numbers, multiply each pair in parallel, and continue until only one number remains.

Consider another example. Given an integer matrix \(A\), suppose we wish to compute its determinant; we refer to this as the DET problem. Sequentially, the determinant can be computed efficiently using Gaussian elimination. More surprisingly—and this is far from obvious—the problem also admits an efficient parallel algorithm (DET \(\in\) NC). (Here are some references: Csanky's paper, Berkowitz' paper.) We will use this statement as a black box many times below.

So, overall the new result states that given a bi-adjacency matrix of a graph, checking whether it has a perfect matching or not can be solved efficiently by a parallel algorithm.

Why it matters: TL;DR

BPM is an extremely well-studied graph problem because it arises naturally in many practical scenarios. The problem has been a focus of intense research for more than 5 decades. (See an excellent introduction to matching and related problems here and here.)

Derandomization is a central problem in theoretical computer science. (For a deep dive into derandomization see this or this survey.) It asks whether randomness truly adds computational power or merely provides a convenient shortcut. Bipartite Perfect Matching has long been known to admit a randomized NC algorithm. Finding a deterministic NC algorithm for the problem therefore fits naturally into the broader derandomization program. In fact, bipartite perfect matching is one of the most natural and simply stated problems in this setting. Its resolution provides a particularly striking example of randomness being removed from an efficient parallel algorithm.

How did the authors solve the problem?

Polynomial-time algorithms for this problem---Kuhn's algorithm, Hopcroft--Karp, or matching-via-max-flow with Ford--Fulkerson---are a staple of undergraduate algorithms courses and have been known since the 1960s. They work by repeatedly finding an augmenting path: a path between two unmatched vertices that alternates between edges outside and inside the current matching; augmenting along it grows the...