Answer: Polynomial-time solvable: the problem belongs to \(\mathrm{P}\), with running time \((m+\tau+L)^{O(1)}\) bit operations.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximate$h$-MaxKEI can be solved in polynomial time in the Silver Bullet model.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support \(T\) of patient–donor pair types with rational masses \(\mu_t\ge 0\) and \(\sum_t\mu_t=1\), directed compatible and half-compatible arcs \(C,H\subseteq T\times T\), no inherently incompatible arcs, and rational bounds \(q,\rho\in[0,1]\), does there exist nonnegative mass flow \(x_{ab}\) on \(C\cup H\) such that, for each \(t\in T\), \(\sum_b x_{tb}=\sum_a x_{at}\le\mu_t\), \(\sum_{(a,b)\in H}x_{ab}\le q\), and \(\sum_{(a,b)\in C}x_{ab}\ge\rho\)? Here \(x_{ab}\) is the mass of type-\(a\) donors assigned to type-\(b\) recipients; the balance constraints make participating pair mass both donate and receive, and a feasible circulation decomposes into exchange cycles.
A society is given by its support: a nonempty list \(T\) of \(\tau\) patient–donor pair types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Explicit directed arc sets \(C,H\) partition \(T\times T\): every donor–recipient combination is compatible or half-compatible, with no inherently incompatible combinations. An arc \((a,b)\) assigns a type-\(a\) donor to a type-\(b\) recipient; half-compatible transplantation consumes one unit of suppressant per unit mass, while compatible transplantation consumes none.
There are no unpaired recipients or altruistic donors. Mass is divisible, cycles have unrestricted length, and loops represent within-type transplantation. Unused pair mass may abstain; participating pair mass must both donate and receive.
Given binary rational bounds \(q,\rho\in[0,1]\), feasibility means existence of real flows \(x_{ab}\ge0\) satisfying
\(\sum_{b\in T}x_{tb}=\sum_{a\in T}x_{at}\le\mu_t\quad(t\in T),\qquad \sum_{(a,b)\in H}x_{ab}\le q,\qquad \sum_{(a,b)\in C}x_{ab}\ge\rho.\)
Let \(m=|C|+|H|\), and let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this mass-flow feasibility problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For discrete patient–donor pairs with unrestricted exchange cycles and no inherently incompatible combinations, deciding whether at least a specified number receive compatible kidneys using at most a specified number of suppressants is polynomial-time solvable ([source](https://arxiv.org/pdf/2103.02253)).
No prior result settling exactly the continuous problem above was identified in the literature search.
The mass-flow feasibility problem is in \(\mathrm{P}\). It can be decided exactly in \((m+\tau+L)^{O(1)}\) bit operations by rational linear programming.
This conclusion applies to the stated continuous model, including binary rational masses, abstention, unrestricted cycles, and loops.
Index the types by \(\{1,\ldots,\tau\}\). Introduce one real variable \(x_{ab}\) for each arc \((a,b)\in C\cup H\). There are exactly \(m\) variables; because \(C,H\) partition \(T\times T\), we also have \(m=\tau^2\).
Consider the following linear system:
These are exactly the constraints in the question: balance makes the incoming and outgoing mass equal, and the capacity inequality bounds their common value.
Replacing each balance equality by two inequalities produces a system \(Ax\le b\) with \(m\) variables and \(m+3\tau+2\) inequalities. Every entry of \(A\) belongs to \(\{-1,0,1\}\). A loop variable cancels in its balance equation but remains in its capacity and transplantation constraints, as required.
Thus the original instance is feasible if and only if this rational linear system is feasible. No relaxation or approximation has been introduced.
We use the polynomial-time rational linear-programming feasibility theorem:
Given a finite system of non-strict linear inequalities with binary rational coefficients, one can decide whether it has a real solution in time polynomial in its total binary encoding length.
This is the rational-input form of [Khachiyan’s polynomial-time linear-programming theorem](https://www.mathnet.ru/eng/dan42319). It decides feasibility exactly, including when the feasible set has empty interior or feasibility requires equality at a bound.
All hypotheses hold here: the system is finite, its coefficients and right-hand sides are rational, and every constraint is non-strict.
Let \(B\) be the binary length of a dense encoding of the constructed system. The coefficient matrix has \(m(m+3\tau+2)\) entries of constant encoding length. The nonconstant right-hand sides are the given masses and bounds, whose total encoding length is at most \(L\). Consequently,
\(B=O(m^2+m\tau+L)\).
Constructing this dense system takes \(O(m^2+m\tau+L)\) bit operations using fixed-width encodings for the constant matrix entries. Applying exact rational LP feasibility therefore takes
\((m^2+m\tau+L)^{O(1)}=(m+\tau+L)^{O(1)}\)
bit operations. Because the arcs are listed explicitly, \(m,\tau=O(L)\), so this is also \(L^{O(1)}\).
In particular, the algorithm never expands a binary rational mass into individual patient–donor pairs.
Although feasibility is already defined by the displayed constraints, their interpretation as divisible exchanges can also be verified.
Let \(x\) be any nonnegative balanced flow. If a positive-flow arc exists, follow positive-flow arcs from it. Whenever a vertex is reached along such an arc, its incoming flow is positive; balance implies that its outgoing flow is positive, so continuation is possible. Since there are finitely many vertices, this walk contains a directed cycle, possibly a loop.
For a simple directed cycle \(K\), let \(\delta=\min_{e\in K}x_e>0\). Subtract \(\delta\) from every arc of \(K\). The residual flow remains nonnegative and balanced: each vertex on the cycle loses equal incoming and outgoing mass. At least one positive arc disappears.
Repeating this operation terminates after at most \(m\) subtractions and gives a decomposition
\(x=\sum_{i=1}^{k}\delta_i\mathbf{1}_{K_i}\), with \(k\le m\).
At each type, the total participating cycle mass equals its outgoing flow and hence is at most \(\mu_t\). Divisibility permits allocating this mass among the cycles; the remaining mass abstains. Both suppressant consumption and compatible-transplant mass are preserved because they are linear sums of arc flows.
Thus unrestricted cycles create no additional constraint beyond the polynomial-size flow system.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The output establishes exact polynomial-time feasibility for the stated continuous model. No major or minor mathematical issues were found.
There is one variable \(x_{ab}\) for each listed arc. Since \(C,H\) partition \(T\times T\), there are exactly \(m=\tau^2\) variables. The indexing uses the support size \(\tau\), as required.
The constraints reproduce the task exactly. Balance equates incoming and outgoing participating mass; the outgoing capacity therefore bounds their common value. The suppressant inequality counts precisely the half-compatible flow. Negating the compatible-flow target correctly turns its lower bound into an upper-bound inequality.
Consequently, both directions of the asserted feasibility equivalence hold directly from the definitions. No integrality assumption, discretization, or additional restriction is introduced.
Nonnegativity contributes \(m\) inequalities, balance contributes \(2\tau\), capacity contributes \(\tau\), and the two global bounds contribute two. The stated total \(m+3\tau+2\) is correct.
Every coefficient belongs to \(\{-1,0,1\}\). In a balance row, a loop contributes once positively and once negatively, giving coefficient zero. Its coefficient in the capacity row remains one, and it contributes to the appropriate transplantation constraint. Thus loops are handled correctly.
The prover states the needed theorem precisely: feasibility of a finite system of non-strict inequalities with binary rational coefficients can be decided in time polynomial in its encoding length. This is the standard exact rational-input consequence of [Khachiyan’s polynomial-time linear-programming theorem](https://www.mathnet.ru/eng/dan42319).
Its hypotheses are satisfied as written: the system is finite, all matrix entries and right-hand sides are rational, and every inequality is non-strict. Real-valued variables are within the theorem’s scope. Neither nonempty interior nor strict feasibility is required, so balance equalities and boundary-only feasibility cause no gap.
The dense coefficient matrix has \(m(m+3\tau+2)\) entries, each requiring constant space. The input supplies the nonconstant right-hand sides with total binary length at most \(L\). Constant right-hand sides and dimension metadata are absorbed into the stated bound because \(m\ge1\). Hence
\(B=O(m^2+m\tau+L)\) is valid.
Writing this matrix with fixed-width constant entries and copying the rational bounds supports the stated construction bound. Applying polynomial-time rational LP feasibility then gives
\((m^2+m\tau+L)^{O(1)}=(m+\tau+L)^{O(1)}\)
bit operations. This equality expresses equivalent polynomial bounds, rather than a particular polynomial exponent.
Explicit arc lists and the nonempty support list imply \(m,\tau=O(L)\), so the resulting bound is also \(L^{O(1)}\). No expansion of rational masses into discrete pairs is needed.
This section is supplementary because the task already defines feasibility through the flow constraints, but its argument is correct.
Positive incoming flow at a reached vertex implies positive outgoing flow by balance. A walk can therefore continue until a vertex repeats, yielding a directed cycle; the segment ending at the first repetition is simple, including the possible loop case.
Subtracting the minimum positive flow on that cycle preserves nonnegativity and balance. At least one positive arc vanishes, and no zero arc becomes positive. Thus there are at most \(m\) subtractions, and termination leaves zero residual flow. The stated decomposition follows.
The cycle allocations respect each type’s capacity because their total participating mass equals its outgoing flow. Divisibility permits these allocations, and abstention accounts for the remainder. Both global quantities are preserved by linearity.
The argument covers \(\tau=1\), empty \(C\) or empty \(H\), zero budgets or targets, and equality at capacity or budget bounds. Empty sums and zero coefficient rows remain valid LP constraints.
The proof resolves the continuous problem directly and does not depend on the cited discrete result. No additional clarification or repair is necessary.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.