Deterministic polynomial-time exact bipartite matching

Deterministic polynomial-time exact bipartite matching

Definitions and mathematical statement

Given a finite simple bipartite graph $G=(U\sqcup V,E)$, a coloring $c:E\to\{\mathrm{red},\mathrm{blue}\}$, and a binary integer $k$, ask whether there exists a perfect matching $M$ with \[ \#\{e\in M:c(e)=\mathrm{red}\}=k. \] The target is a deterministic algorithm deciding this in time polynomial in the total explicit input bit length. It must report No when the parts have different sizes or $k\notin\{0,\ldots,|U|\}$. This is an exact color-count constraint, not minimization of red edges or deciding whether at most $k$ are used. A matching need not be output by the selected decision formulation.

Formulation and concept references: [S1].

Short English statement

Can one decide deterministically in polynomial time whether a red-blue bipartite graph has a perfect matching with exactly a prescribed number of red edges?

Research attempt

Scope, process, and first gap.

This attempt by GPT-6 Astra Ultra, dated 27 September 2026, derives a determinant identity-testing formulation, reconstructs a randomized polynomial-time decision algorithm, and proves a deterministic algorithm for maximum-degree-two instances. The source [S1] explicitly distinguishes exact color counts from ordinary bipartite perfect matching and records the randomized bound.

The first gap is a deterministic polynomial-time way to avoid cancellations in the relevant determinant coefficient for arbitrary input graphs. The existence of a perfect matching with a minimum or maximum number of red edges does not answer the exact-count question.

Basic cases and a gap in attainable counts.

Reject immediately if $|U|\ne|V|$ or the binary integer $k$ lies outside $[0,|U|]$. If both parts are empty, the empty matching is perfect and has exactly zero red edges, so the answer is Yes precisely for $k=0$.

For a nonempty countertest, take $K_{2,2}$, color the two diagonal edges red and the two off-diagonal edges blue. Its only perfect matchings are the diagonal pair and the off-diagonal pair. Their red counts are two and zero. Thus the attainable counts need not form an interval: the minimum is zero and the maximum is two, but $k=1$ is impossible.

The same example invalidates a direct linear-programming integrality argument. The midpoint of the two permutation matrices is a fractional perfect matching using red mass one. Adding the equality that red mass is one therefore creates a feasible fractional point when no integral solution exists. Total unimodularity of the original bipartite matching constraints does not automatically survive the additional color-count row.

A coefficient with one distinct monomial per matching.

Assume $|U|=|V|=n$, and introduce an indeterminate $X_e$ for every edge, along with a variable $z$. Define \[ B_{ij}(z)= \begin{cases} X_{ij}z,&ij\in E\text{ is red},\\ X_{ij},&ij\in E\text{ is blue},\\ 0,&ij\notin E. \end{cases} \] Expanding the determinant gives \[ [z^k]\det B(z) =F_k(X) =\sum_{\substack{M\text{ perfect}\\|M\cap E_{\rm red}|=k}} \operatorname{sgn}(M)\prod_{e\in M}X_e. \tag{289.1} \] Different matchings have different edge sets, and hence different monomials. Each coefficient is $1$ or $-1$, so no two matching terms cancel as a formal polynomial. It follows that \[ F_k\not\equiv0 \quad\Longleftrightarrow\quad \text{the requested matching exists}. \] The equivalence holds over any field, including characteristic two: signs may coincide there, but distinct monomials remain distinct.

The total degree of $F_k$ is $n$. This algebraic encoding retains the exact red count through the coefficient in $z$, rather than turning it into a weighted minimum problem.

The randomized test with its one-sided error proved.

Choose a prime $p>3n$ and assign every $X_e$ independently and uniformly in $\mathbb F_p$. Such a prime of size $O(n)$ can be found by elementary polynomial-time search; small exceptional values of $n$ can be handled directly. Evaluate the coefficient $F_k$ at this assignment.

A nonzero polynomial of total degree at most $n$ vanishes at a uniform point with probability at most $n/p<1/3$. Here is the standard induction behind that bound. Regard it as a polynomial of degree $d$ in its last variable with nonzero leading coefficient $Q$ in the others. By induction the leading coefficient vanishes with probability at most $(n-d)/p$. When it does not vanish, the resulting one-variable polynomial has at most $d$ roots. Adding the two failure probabilities proves the claim.

If no required matching exists, $289.1$ is identically zero and the test never falsely answers Yes. If one exists, the test finds a nonzero value with probability greater than $2/3$. This is the one-sided randomized guarantee recorded in [S1].

Computing the coefficient uses only polynomially many field operations. After fixing the $X_e$, the determinant is a polynomial in $z$ of degree at most $n$. Evaluate it at $n+1$ distinct field elements, compute each numeric determinant by elimination, and interpolate. The field is large enough for those distinct points. Field elements have $O(\log n)$ bits, so this is polynomial in the explicit input bit length.

Why setting all auxiliary variables to one fails.

Take $K_{2,2}$ with every edge red. Both perfect matchings have the required red count two, but after $X_e=1$ the matrix is \[ \begin{pmatrix}z&z\\z&z\end{pmatrix}, \] whose determinant is zero. The two matching signs cancel. Thus the variables in $289.1$ are not decorative: they prevent formal cancellation before a suitable evaluation is chosen.

Similarly, the permanent would count matching terms with positive signs, but replacing a polynomial-time determinant calculation by an unproved polynomial-time permanent computation does not supply an algorithm. Existence of a positive combinatorial sum does not make its efficient evaluation automatic.

A complete deterministic restricted class.

Suppose the bipartite graph has maximum degree at most two. Its connected components are isolated vertices, paths, and even cycles. An isolated vertex immediately precludes a perfect matching. A path with an odd number of vertices has none; a path with an even number has exactly one, forced successively by its endpoints.

An even cycle has exactly two perfect matchings, its alternating edge sets. Let their red counts be $a_j,b_j$. Add the forced path counts to a total $r_0$. The exact question now becomes whether \[ k-r_0\in\left\{\sum_j c_j:c_j\in\{a_j,b_j\}\right\}. \] Maintain a Boolean array of reachable totals between zero and $n$. Start with total zero and, for each cycle, replace the set $S$ by $(S+a_j)\cup(S+b_j)$. At most $n$ cycles occur, so this uses polynomial time and space.

All red counts are bounded by the number of matching edges, hence by the explicit graph size. There is no binary-weight subset-sum blowup hidden in this dynamic program. The arbitrary binary input $k$ was already range-checked. Distinct components are independent because a perfect matching cannot use edges between them.

This also explains the two-by-two gap example: one cycle offers counts zero and two, and the reachable-total array correctly omits one. For forests, the same endpoint argument yields at most one perfect matching per component; the two-choice cycles are the only source of branching in this subclass.

A sufficient deterministic isolation route.

Suppose one could compute polynomially bounded integer weights $w_e\ge0$ so that, whenever a matching with red count $k$ exists, exactly one such matching minimizes $\sum_{e\in M}w_e$. Substitute $X_e=t^{w_e}$ in $289.1$. The coefficient of the smallest occurring power of $t$ is then $1$ or $-1$ and cannot cancel.

Since the weights and $n$ are polynomially bounded, the determinant has polynomial degree in both $z$ and $t$. Bivariate interpolation over a sufficiently large field would decide nonzeroness in deterministic polynomial time. Thus such a uniform isolation procedure is a concrete sufficient missing ingredient.

Assigning exponentially separated weights, such as $w_e=2^{j(e)}$, makes every subset weight different and does isolate. But the resulting polynomial degree is exponential in the number of edges. Writing an exponent in binary does not make interpolation through that degree polynomial-time. Evaluating at a fixed integer can likewise create numbers with exponentially many bits. This obvious isolation construction therefore fails the required bit complexity.

Verification and outcome.

The checks enumerate all perfect matchings of small colored bipartite graphs, compare their red counts with the formal determinant monomials, and test the dynamic program on paths and cycles. The cancellation and fractional-midpoint examples are checked exactly. Random trials are not used as proof of a deterministic algorithm.

UNRESOLVED. The algebraic one-sided randomized algorithm and the degree-two deterministic subclass are established. The first remaining gap is deterministic polynomial-time coefficient nonzeroness or an equivalent combinatorial method for unrestricted bipartite graphs. Neither attainable-count extrema nor an unchecked determinant specialization closes it.

Sources

• S1 Antoine Amarilli, List of open questions, Complexity of the exact bipartite matching problem; complete section read September7,2026. https://a3nm.net/work/research/questions/. Formulation source.