Planar Graph Perfect Matching Is in NC
- 30 May 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 67 (4), 1-34
- https://doi.org/10.1145/3397504
Abstract
Is perfect matching in NC? That is, is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in theoretical computer science for over three decades, ever since the discovery of RNC perfect matching algorithms. Within this question, the case of planar graphs has remained an enigma: On the one hand, counting the number of perfect matchings is far harder than finding one (the former is #P-complete and the latter is in P), and on the other, for planar graphs, counting has long been known to be in NC whereas finding one has resisted a solution. In this article, we give an NC algorithm for finding a perfect matching in a planar graph. Our algorithm uses the above-stated fact about counting perfect matchings in a crucial way. Our main new idea is an NC algorithm for finding a face of the perfect matching polytope at which a set (which could be polynomially large) of conditions, involving constraints of the polytope, are simultaneously satisfied. Several other ideas are also needed, such as finding, in NC, a point in the interior of the minimum-weight face of this polytope and finding a balanced tight odd set.Keywords
Funding Information
- NSF (CCF-1815901)
- DIMACS/Simons Collaboration on Bridging Continuous and Discrete Optimization (CCF-1740425)
This publication has 21 references indexed in Scilit:
- NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problemsInformation and Computation, 1989
- Parallel algorithms for minimum cuts and maximum flows in planar networksJournal of the ACM, 1987
- Random generation of combinatorial structures from a uniform distributionTheoretical Computer Science, 1986
- Parallel algorithms for tree traversalsParallel Computing, 1985
- Parallel computation for well-endowed rings and space-bounded probabilistic machinesInformation and Control, 1983
- The complexity of restricted spanning tree problemsJournal of the ACM, 1982
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Fast Parallel Matrix Inversion AlgorithmsSIAM Journal on Computing, 1976
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965
- Paths, Trees, and FlowersCanadian Journal of Mathematics, 1965