In a recent preprint (Chatterjee et al. 2026), Chatterjee, Ghosh, Gurjar, Raj, and Thierauf developed an algorithm for finding a maximum-cardinality matching in a bipartite graph. This resolves one of the central open questions in the theory of deterministic parallel computation.
Modern computers contain many processors, so it is natural to ask which algorithmic tasks can be efficiently parallelized. Informally, a problem is efficiently parallelizable if a large number of processors can work simultaneously and finish the computation much faster than any known sequential algorithm. Formally, a decision problem belongs to the class if it can be solved by a deterministic parallel algorithm in polylogarithmic time using polynomially many processors. It follows directly from the definition that .
Strictly speaking, is a class of decision problems. For search problems, however, we will use the standard abuse of terminology and say that a search problem is in if its output can be produced within the same parallel resource bounds. The class contains many basic arithmetic problems, such as integer addition, multiplication, and division. For many other problems in , however, the existence of a deterministic polylogarithmic-time parallel algorithm is far from obvious.
A particularly important example is the problem of finding a maximum-cardinality matching in a graph . Recall that a matching is a set of edges no two of which share a common vertex. The maximum-cardinality matching problem asks, given , to return a matching with as many edges as possible. If has vertices, then every matching has size at most . A matching of size exactly is called a perfect matching; of course, such a matching can exist only when is even.
The first polynomial-time algorithm for finding a maximum-cardinality matching in a general graph was developed by Edmonds (Edmonds 1965) in 1965. In 1980, Micali and Vazirani (Micali and Vazirani 1980; Vazirani 2020) gave an algorithm running in time on -vertex graphs with edges. In 2004, Mucha and Sankowski (Mucha and Sankowski 2004) developed a randomized algorithm running in time , where is the exponent of matrix multiplication, currently known to be less than . This algebraic algorithm is faster than the algorithm on sufficiently dense graphs, namely when .
The randomized parallel history of the problem begins with the work of Lovász (Lovász 1979), who gave a randomized parallel algorithm for the decision version: given a graph and a positive integer , decide whether has a matching of size at least . The class of problems admitting randomized polylogarithmic-time parallel algorithms with polynomially many processors is called . Lovász’s algorithm, however, does not output a matching. In 1986, Karp, Upfal, and Wigderson (Karp et al. 1986) proved that the corresponding search problem also belongs to : one can construct a maximum-cardinality matching by a randomized parallel algorithm. Later, Mulmuley, U. Vazirani, and V. Vazirani (Mulmuley et al. 1987) gave a cleaner and faster algorithm for the same problem.
Standard derandomization conjectures would imply , but this equality remains open. Consequently, maximum-cardinality matching in general graphs has long been one of the most prominent problems known to be in but not known to be in . For general graphs, the best deterministic parallel result currently known is due to Svensson and Tarnawski (Svensson and Tarnawski 2017): the problem can be solved by a deterministic parallel algorithm running in time using processors. Thus the running time is polylogarithmic, but the number of processors is quasi-polynomial rather than polynomial.
The difficulty of the general problem motivates the study of special graph classes, such as planar graphs and bipartite graphs. For planar graphs, much of the work focused first on the apparently simpler task of finding a perfect matching, if one exists. In 1989, Vazirani (Vazirani 1989) proved that the seemingly harder problem of counting perfect matchings in planar graphs is in . In 1995, Miller and Naor (Miller and Naor 1995) developed an algorithm for finding a perfect matching in bipartite planar graphs. Mahajan and Varadarajan (Mahajan and Varadarajan 2000) later gave a conceptually different algorithm for the same problem, using the algorithm for counting perfect matchings as a subroutine.
In 2020, Anari and Vazirani (Anari and Vazirani 2020) proved the analogous search result for general planar graphs.
The proof of Theorem uses the counting subroutine for planar perfect matchings and extends ideas of Mahajan and Varadarajan (Mahajan and Varadarajan 2000). The non-bipartite case requires additional structural ingredients, in particular the use of tight odd sets in the planar perfect matching polytope.
However, Theorem concerns only perfect matchings. It does not give an algorithm for finding a maximum-cardinality matching when no perfect matching exists. In fact, for non-bipartite planar graphs, it remains open whether maximum-cardinality matching is in deterministic .
For bipartite graphs, the situation has now changed. In a 2026 preprint, Chatterjee, Ghosh, Gurjar, Raj, and Thierauf (Chatterjee et al. 2026) resolved the deterministic parallel complexity of bipartite matching.
Theorem is a major advance because it removes randomness from one of the classical parallel algorithms for matching. Before this work, bipartite matching was known to have efficient randomized parallel algorithms, but no deterministic algorithm was known for the full maximum-cardinality problem. The new result shows that, at least in the bipartite case, the randomness used in earlier parallel matching algorithms is not essential.
This also clarifies the landscape around matching problems. Perfect matching in planar graphs is in , maximum-cardinality matching in bipartite graphs is now in , and maximum-cardinality matching in general graphs remains one of the central unresolved problems in deterministic parallel computation. The remaining gap is therefore not merely technical: it marks the boundary between what is currently understood and what is still mysterious about the parallel structure of matching.