Perfect matching in NC: derandomising the isolation lemma for bipartite and general graphs

Known. Mulmuley, Vazirani and Vazirani (Combinatorica 1987) and Karp, Upfal and Wigderson (1986) gave RNC algorithms. Fenner, Gurjar and Thierauf (STOC 2016, arXiv:1601.06319) gave a deterministic quasi-NC algorithm for bipartite perfect matching by constructing a poly-size family of weight functions, one of which is isolating, and as a consequence NC algorithms for planar bipartite graphs. Svensson and Tarnawski (FOCS 2017, arXiv:1704.01929) extended to general graphs, by a more involved isolation argument; they stated getting from quasi-NC to NC as the most immediate open question, even for bipartite graphs, and noted that the number of weight functions in the construction ($\log n$ rounds) is the obstacle. Anari and Vazirani (arXiv 2017; FOCS 2018, J. ACM 2020) proved that planar perfect matching is in NC, and Eppstein and Vazirani (SPAA 2019; SIAM J. Comput. 2021) extended NC algorithms to one-crossing-minor-free graphs, which include $K_{3,3}$-free graphs. Exact matching (a perfect matching with a prescribed number of red edges) is in RNC with no known deterministic polynomial-time algorithm, let alone NC; an unrefereed AI-generated manuscript in OpenAI's October 2026 release claims a randomised almost-linear-time sequential algorithm for it, which does not bear on derandomisation. No 2025–26 result improving the quasi-NC bounds was found.

NC algorithms for matching would complete the picture of parallel complexity of combinatorial optimisation (matching, flows, matroid problems are the standard test cases for derandomising the isolation lemma). It would also imply deterministic algorithms for related search problems that reduce to matching, but a quasi-NC algorithm is already almost as good in theory; practical parallel matching uses randomised or heuristic algorithms.

A deterministic algorithm for bipartite (or general) perfect matching with $\mathrm{poly}(n)$ processors and $\mathrm{polylog}(n)$ depth, with proof. Partial progress: NC for a new graph class, or an NC algorithm for the decision problem alone.