Deterministic NC perfect matching

Four vertices form a path A–B–C–D. Choosing AB and CD pairs every vertex exactly once. In a four-vertex star, with links from A to B, C and D only, this cannot be done: every possible pair uses A.

For any undirected graph, can a deterministic procedure find such a complete pairing, or report that none exists, with a polynomial number of processors and only a number of parallel rounds bounded by a fixed power of the logarithm of the input size? The question is about both the pairing and those resource limits.[1]

Can an algorithm always find a complete pairing along existing graph edges, or certify that no such pairing exists, using a controlled amount of parallel work and a short chain of dependencies without randomness? On A–B–C–D, the edges AB and CD form a perfect matching. In the star with center A and leaves B, C and D, every edge uses A, so no perfect matching exists.

NC requires polynomially many processors and parallel time bounded by a fixed power of the logarithm of the input length. The target includes arbitrary finite undirected graphs and the search output, not only a yes/no answer. A bipartite graph has a division into two parts with all edges crossing between them; general graphs need not have such a division. The 2026 bipartite NC claim therefore concerns a restricted graph family.[1] [2]

The general-graph NC algorithm is not known.[1]

The cited July revision of the bipartite preprint claims deterministic NC search in that graph class. It does not cover arbitrary undirected graphs. Known deterministic quasi-NC permits more than polynomially many processors, so it does not meet the NC requirement.

The catalytic-logspace report works in another model, with extra memory whose contents must be restored. Its matching results do not supply the deterministic NC algorithm asked for here.[1] [2]

Choosing an edge rules out other edges sharing either endpoint. The local choices therefore have to fit into one global pairing. This makes matching a way to study whether many simultaneous computations can resolve conflicts without a long chain of dependent choices or random decisions.[1]

There is a connection between constructing a matching and deciding whether one exists. A sequential construction can test an edge and then solve a smaller decision problem, repeating as choices are fixed. Even if each decision is fast in parallel, a long sequence of dependent tests need not be fast in parallel overall.

Derandomization for this target must therefore preserve more than correctness: it must coordinate construction while retaining both the short parallel time and the polynomial processor bound. Matching supplies a concrete setting in which local feasibility, global consistency and the organization of dependencies meet.[1] [2]