Deterministic parallel perfect matching in general graphs
Let $G = ([n], E)$ be a finite simple undirected graph on $[n] = \{1, \dots, n\}$, $n \ge 2$, given by its $\binom{n}{2}$ adjacency bits. Uniform $\mathrm{NC}$ is understood as follows: a family $(C_n)_{n \ge 2}$ of Boolean circuits with fan-in-two AND and OR gates, NOT gates and constants, with $$\operatorname{size}(C_n) \le K n^c, \qquad \operatorname{depth}(C_n) \le K \bigl(\log_2(n + 2)\bigr)^k$$ for absolute constants $K, c, k > 0$, which is logspace-uniform: one deterministic machine writes $C_n$ on input $1^n$ using $O(\log n)$ work space. Karp, Upfal and Wigderson, and Mulmuley, Vazirani and Vazirani, gave randomized NC algorithms that find a perfect matching. Svensson and Tarnawski gave a deterministic parallel algorithm that runs in $O(\log^3 n)$ time on $n^{O(\log^2 n)}$ processors. Anari and Vazirani showed that perfect matchings in planar graphs can be found in NC, and that a minimum-weight perfect matching in a general graph with polynomially bounded edge weights can be found in NC given an oracle that decides whether there is a perfect matching of weight at most a given number. Chatterjee, Ghosh, Gurjar, Raj and Thierauf show that bipartite matching, including its search version, is in NC (2026 preprint).
Problem. Is there such a logspace-uniform circuit family that, on every input graph $G$, outputs a success bit and an edge-incidence vector, where the success bit is $1$ exactly when $G$ has a perfect matching and, in that case, the vector encodes a perfect matching of $G$? No promise is made on $G$ (bipartiteness, planarity, bounded degree or uniqueness of the matching).
Source: The question whether the randomized NC algorithms of Karp, Upfal and Wigderson (1986) and of Mulmuley, Vazirani and Vazirani (1987) can be made deterministic; see Svensson and Tarnawski (2017), §1, and Anari and Vazirani (2020). Stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- OC
- Keywords
- AIM Open Applied Problems, derandomization, parallel algorithms, perfect matchings
References
@article{karp1986,
author = {Karp, Richard M. and Upfal, Eli and Wigderson, Avi},
title = {Constructing a perfect matching is in random {NC}},
journal = {Combinatorica},
volume = {6},
number = {1},
year = {1986},
pages = {35--48},
doi = {10.1007/BF02579407},
}
@article{mulmuley1987,
author = {Mulmuley, Ketan and Vazirani, Umesh V. and Vazirani, Vijay V.},
title = {Matching is as easy as matrix inversion},
journal = {Combinatorica},
volume = {7},
number = {1},
year = {1987},
pages = {105--113},
doi = {10.1007/BF02579206},
}
@inproceedings{svensson2017,
author = {Svensson, Ola and Tarnawski, Jakub},
title = {The matching problem in general graphs is in quasi-{NC}},
booktitle = {2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)},
publisher = {IEEE},
year = {2017},
pages = {696--707},
doi = {10.1109/FOCS.2017.70},
eprint = {1704.01929},
archivePrefix = {arXiv},
}
@inproceedings{anari2020matching,
author = {Anari, Nima and Vazirani, Vijay V.},
title = {Matching is as easy as the decision problem, in the {NC} model},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
series = {LIPIcs},
volume = {151},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2020},
pages = {54:1--54:25},
doi = {10.4230/LIPIcs.ITCS.2020.54},
eprint = {1901.10387},
archivePrefix = {arXiv},
}
@article{anari2020planar,
author = {Anari, Nima and Vazirani, Vijay V.},
title = {Planar graph perfect matching is in {NC}},
journal = {J. ACM},
volume = {67},
number = {4},
year = {2020},
pages = {1--34},
doi = {10.1145/3397504},
}
@techreport{chatterjee2026,
author = {Chatterjee, Abhranil and Ghosh, Sumanta and Gurjar, Rohit and Raj, Roshan and Thierauf, Thomas},
title = {Bipartite matching is in {NC}},
institution = {Electronic Colloquium on Computational Complexity},
type = {ECCC Report},
number = {TR26-100},
year = {2026},
note = {Revision 2, 15 July 2026},
url = {https://eccc.weizmann.ac.il/report/2026/100/},
}
@misc{aim-general-graph-perfect-matching-nc,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Deterministic parallel perfect matching in general graphs}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/490-general-graph-perfect-matching-nc.md},
note = {Entry 490 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00349, "Deterministic parallel perfect matching in general graphs", clopen.solutions.