On the CGGRT Criterion for Detecting Bipartite Perfect Matchings in NC
Computational ComplexityData Structures and Algorithms
Summary
The authors discuss a recent important result by Chatterjee, Ghosh, Gurjar, Raj, and Thierauf, who created the first fast and predictable (deterministic NC) method to find perfect matchings in bipartite graphs. Their work means you can quickly check and find perfect matchings using parallel computing. In this note, the authors offer a simpler way to explain the detection method from the original work, and they improve some of its technical details.
Authors
Swastik Kopparty, Shubhangi Saraf
Abstract
The recent breakthrough work of Chatterjee, Ghosh, Gurjar, Raj and Thierauf [CGGRT26] gives the first deterministic NC algorithm for the bipartite matching problem. They show how to detect as well as find perfect matchings in bipartite graphs in NC. In this note we present an arguably simpler-to-state variation of the NC detection criterion of [CGGRT26], with improved parameters.