Perfect-Matching Search in Deterministic NC (General Graphs)

Perfect-Matching Search in Deterministic NC (General Graphs)

Definitions and mathematical statement

A perfect matching in a finite simple undirected graph is a set of disjoint edges covering every vertex. On the adjacency-matrix encoding of a labeled $n$-vertex graph, seek one logspace-uniform family of deterministic Boolean circuits that outputs a matching matrix, or a distinguished NO flag precisely when no perfect matching exists. With fan-in at most two for AND and OR, the bounds are \[ \operatorname{size}(C_n)\le Cn^c,\qquad \operatorname{depth}(C_n)\le C(\log(n+2))^k \] for constants independent of $G,n$. A logarithmic-space transducer must print $C_n$ from $1^n$, including its designated outputs. This is a multi-output search problem on general graphs, not just testing existence or treating bipartite graphs.

Formulation and concept references: [S1].

Short English statement

Can perfect matchings be found deterministically in general graphs by uniform polynomial-size circuits of polylogarithmic depth?

Research attempt

Current frontier.

Svensson--Tarnawski obtain deterministic quasi-NC for general-graph matching: polylogarithmic parallel time with quasipolynomially many processors. Polynomial size is the missing requirement, not merely polylogarithmic depth. Their use of odd-set constraints and laminar faces cannot be replaced by a bipartite argument without further work. [S1], Abstract and Introduction. The isolating-weights method originates in Mulmuley--Vazirani--Vazirani's randomized parallel algorithm. [E1]. A 2025 manuscript revised in August 2026 gives a randomized matrix-multiplication-time algorithm for the red-edge-count version of Exact Matching; it is a different problem and does not supply the deterministic uniform circuits here. [E3], Abstract. The attempt below isolates the uniform construction step instead of claiming that a probabilistically existing list is already an algorithm.

Attack route.

A decision-to-search self-reduction can require linearly many dependent rounds. A parallel algebraic extraction is possible once a common minimum matching is isolated; without isolation different processors can make incompatible choices. The route pursued here combines a short list of weight assignments, parallel determinant computations and an explicit verification circuit. The main question becomes whether the list can be generated uniformly, with both its length and its weight magnitudes polynomially bounded. We first prove its nonuniform existence and then show exactly why that does not close the target.

Attempt.

1. State the missing list construction precisely. Consider the following sufficient hypothesis, for some fixed $c,k$: there is a logspace-uniform deterministic circuit family of polynomial size and depth $O(\log^k n)$ which, from the adjacency matrix of $G$, outputs a list of at most $n^c$ assignments \[ w^{(r)}:E(G)\longrightarrow\{1,\ldots,n^c\}. \] Whenever $G$ has a perfect matching, at least one assignment makes its minimum-weight perfect matching unique. No requirement is imposed on a list entry that fails to isolate. Call this hypothesis (ULI). A stronger, input-independent construction would print such a list on the complete graph for each $n$, isolating every subgraph with a perfect matching. That stronger version also suffices, but is not assumed necessary for deterministic NC.

2. Isolated minimum matching gives parallel search, not just decision. Fix one assignment $w$, and form the skew-symmetric polynomial Tutte matrix \[ T_w(t)_{ij}=\begin{cases} t^{w_{ij}},&i<j,\ ij\in E(G),\\ -t^{w_{ij}},&i>j,\ ij\in E(G),\\ 0,&\text{otherwise}. \end{cases} \] For even $n$, its Pfaffian is \[ \operatorname{Pf}(T_w(t))= \sum_{M\text{ perfect}}\operatorname{sgn}(M)t^{w(M)}, \qquad \det T_w(t)=\operatorname{Pf}(T_w(t))^2. \] If $M_*$ is the unique minimum with weight $W$, the coefficient of $t^W$ in the Pfaffian is $1$ or $-1$, so \begin{equation}\label{wsref-0-33-30-30-30-36-38-30-30-3a-76-61-6c-75-61-74-69-6f-6e} \operatorname{val}_t\det T_w=2W. \end{equation} Give the zero polynomial valuation $+\infty$. For every edge $e$, compute also the determinant after deleting $e$. Then \begin{equation}\label{wsref-0-33-30-30-30-36-38-30-30-3a-65-78-74-72-61-63-74} e\in M_* \quad\Longleftrightarrow\quad \operatorname{val}_t\det T_{w,G-e}>\operatorname{val}_t\det T_{w,G}. \end{equation} If $e\notin M_*$, the unique least term survives. If $e\in M_*$, all remaining matchings have strictly greater weight, or none exist. Cancellation among these higher terms cannot create a smaller exponent. This proves (30006800:extract), including the zero-polynomial case. For a nonisolating assignment the extracted edge set may be wrong, so we do not accept it without checking it.

All degrees here are at most $D=n\max w$, a polynomial. One concrete way to perform the polynomial determinant computations is to evaluate at $t=0,1,\ldots,D$ in parallel and interpolate. Each matrix entry has polynomial bit length, and each determinant has bit length at most $O(n\max w\log(D+1)+n\log n)$. Uniform parallel determinant algorithms are available for these integer matrices. [E2], Section 2, Definition 2.6 and Lemma 2.7. For interpolation one may use \[ P(t)=\sum_{j=0}^{D}P(j) \frac{\prod_{0\le r\le D,\ r\ne j}(t-r)} {(-1)^{D-j}j!(D-j)!}. \] A common denominator $D!$ makes all computations integral until a final exact division; coefficient lists, factorials and products have polynomial length and bit size. Balanced addition/multiplication trees and standard uniform integer-arithmetic circuits have polylogarithmic depth. Thus no arithmetic operation on an exponentially long integer is being counted as one Boolean gate.

For every list entry compute (30006800:extract) in parallel, reject it if its original determinant is zero, and verify that the resulting indicator matrix uses graph edges and has exactly one incident selected edge at every vertex. Those tests are uniform NC. Select the first valid entry using prefix OR circuits; if none is valid, output NO. Under (ULI), an existing perfect matching produces at least one valid entry. If no perfect matching exists, no indicator matrix can pass the verification. For odd $n$, output NO directly. This proves that (ULI) implies the precise multi-output, logspace-uniform NC target. All large fan-in conjunctions used in this description are replaced by balanced fan-in-two trees.

3. A polynomial universal list exists nonuniformly. Let $m=\binom n2$, $n\ge2$, and independently assign each of the $m$ possible edges a weight uniformly in $\{1,\ldots,2m\}$. For any fixed nonempty family $\mathcal F$ of edge subsets, its minimum-weight member is unique with probability at least $1/2$. Here is the relevant isolation proof. Fix all weights but that of edge $e$. Let $a$ be the least sum excluding $e$ among members containing $e$, and $b$ the least weight of a member not containing $e$; if either class is empty it cannot cause a tie. There is at most one critical value $w_e=b-a$. If two different global minimizers exist, an edge in their symmetric difference must have this critical value. A union bound over the $m$ possible edges gives failure probability at most $m/(2m)=1/2$. This is the isolating lemma of [E1], specialized with all constants exposed.

Take $m+1$ independent assignments. For any fixed graph with a perfect matching, the probability that every assignment fails to isolate is at most $2^{-(m+1)}$. There are at most $2^m$ labelled graphs. Hence \[ \Pr(\text{some graph is not isolated by the entire list}) \le2^m2^{-(m+1)}<1. \] There therefore exists, for each $n$, a universal list of $m+1$ assignments with weights at most $2m$. Its description length is $O(n^4\log n)$. Hardwiring this list into the circuits of part 2 gives nonuniform polynomial-size, polylogarithmic-depth search circuits. It does not give a logspace transducer printing their descriptions. Enumerating all lists and testing all graphs would eventually find one, but its time, space and circuit size are not those in the target. The attempt stops at that uniformity gap, rather than promoting the union bound to a deterministic parallel construction.

4. Two ways to break an apparent shortcut. First, weights $w_e=2^{\operatorname{index}(e)}$ distinguish every subset and therefore isolate every nonempty family. Their binary encodings have only $O(n^2)$ bits, but the degrees of $T_w(t)$ are exponential. The coefficient-based computation above would have exponentially many output positions. A short encoding of an exponent is not a polynomial degree bound. A compressed-polynomial valuation algorithm with the same NC bounds is not supplied here.

Second, on $K_4$ give every edge weight one. With vertices in their usual order, \[ \operatorname{Pf}(T_w)=t^2-t^2+t^2=t^2. \] Deleting edge $12$, $34$, $14$ or $23$ makes the Pfaffian zero; deleting $13$ or $24$ leaves $2t^2$. The valuation rule would consequently select the four-cycle $\{12,23,34,14\}$, not a matching. The companion check verifies all six deletions exactly. This refutes the rule without its isolation hypothesis; it also explains the need for a final output validator even when a list is guaranteed to contain one good entry.

Stress test.

The Pfaffian is used over characteristic zero, so its signs are not silently discarded. Its polynomial identity does not assert that a single arbitrary numeric substitution witnesses every perfect matching. The determinant routine's ring-operation bounds have been accompanied by degree and bit bounds. All deletions are computed in parallel, not adaptively after an earlier choice of an edge.

The probabilistic argument proves existence of short advice, not uniform NC. Conversely, (ULI) is sufficient but has not been proved necessary: a future deterministic matching algorithm might avoid isolation entirely. Nothing here makes an unweighted decision procedure automatically a polylogarithmic-depth search procedure. Nor has the quasipolynomial resource bound in [S1] been relabelled polynomial.

Outcome.

Outcome: Conditional reduction.

A uniform short-list isolation hypothesis has been shown to imply the exact search relation in the catalogue, including NO outputs, Boolean bit costs and logspace uniformity. The same method yields an elementary nonuniform existence proof with an explicit polynomial advice length. An exact four-vertex test rules out dropping isolation. These are reconstructions and deductions within the notebook, not claims of a new matching complexity theorem.

The missing step is a logspace-uniform polynomial-resource construction of the lists, or a different search method avoiding them. The existence proof by random choice does not provide that construction.

Sources

• S1 Svensson and Tarnawski, The Matching Problem in General Graphs is in Quasi-NC, introduction; FGT Section 2.1 defines Search-PM; Nanongkai–Scquizzato Section 2.2 fixes logspace-uniform NC. https://arxiv.org/pdf/1704.01929. Catalogue formulation source.
• E1 K. Mulmuley, U. V. Vazirani and V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica 7 $1987$, 105--113; isolating lemma and randomized parallel matching method. https://doi.org/10.1007/BF02579206.
• E2 M. Soltys, Berkowitz's algorithm and clow sequences, Electronic Journal of Linear Algebra 9 $2002$, 42--54, Section 2, Definition 2.6 and Lemma 2.7. https://arxiv.org/pdf/math/0201315. Used for the uniform, division-free parallel determinant construction.
• E3 R. Sato and Y. Yamaguchi, Exact Matching in Matrix Multiplication Time, arXiv:2508.04081v2, 10 August 2026, Abstract. https://arxiv.org/abs/2508.04081. The red-edge-count problem and randomized sequential time in this source are not the uniform deterministic NC target. All consulted 27 September 2026.