Answer: —
Theorem 1 — class: other
Given a finite-horizon typed kidney-exchange instance with complete role types \(s\in S\), rational stage masses \(\mu_s^r\), typed compatibility and cycle templates \(c\), and an ABO-feature map \(g:S\to B\), choose vertex potentials \(p_{g(s)}\) and stagewise fractional cycle flows \(y_c^r\) satisfying \(\sum_c a_{s,c}y_c^r\le\mu_s^r\), with worst-case tie-breaking among adjusted-optimal flows, and decide whether \(\operatorname{VAL}_V(I,p)\ge\rho\,\operatorname{OPT}_{\mathrm{fluid}}(I)\); in particular, determine whether Theorem 1's ratios survive when every role mass is scaled by \(M\to\infty\).
A society is given by its support: the list of the \(\tau\) complete role types with positive mass, each mass a binary rational. Support size counts listed types, not possible types. Masses need not sum to \(1\).
An instance \(I\) has horizon \(H\). Each type \(s\in S\) specifies mass \(q_s>0\), arrival and expiration stages \(1\le\alpha_s\le\beta_s\le H\), a patient–donor pair or altruist role, and its typed compatibility. The map \(g:S\to B\) records one of the sixteen patient–donor ABO types or four altruist donor ABO types; compatibility must respect ABO compatibility but may impose additional restrictions.
All feasible typed cycle and chain templates are explicitly listed; let \(m\) be their number. Cycles contain between \(2\) and \(\ell\) pair roles. Chains contain one altruist followed by at least one pair and terminate with the last donor donating to the waiting list; their length cap is \(d\), counting that final donation. Every admissible chain prefix terminating this way is included. A template is available only while all its roles are present.
Let \(a_{s,c}\) count occurrences of role type \(s\) in template \(c\). All transplant weights are \(1\): a cycle's reward \(w_c\) is its length, and a chain involving \(t\) pairs has reward \(t+1\), including the waiting-list transplant. No waiting-list mass is consumed.
At stage \(r\), the residual mass is \(\mu_s^r=q_s-\sum_{u<r,c}a_{s,c}y_c^u\) for active types and \(0\) otherwise. Feasible flows satisfy \(y_c^r\ge0\) and \(\sum_c a_{s,c}y_c^r\le\mu_s^r\); consumption is permanent, and unmatched mass expires after \(\beta_s\).
Choose one fixed vector \(p\in\mathbb R^B\), with full knowledge of \(I\). Before the final stage, clearing maximizes \(\sum_c(w_c-\sum_s a_{s,c}p_{g(s)})y_c^r\); at stage \(H\), it maximizes unadjusted reward. Empty clearing is feasible. Define \(\operatorname{VAL}_V(I,p)\) as the infimum of total unadjusted reward over all histories of stagewise maximizing flows, so tie-breaking is adversarial across the entire horizon.
Define \(\operatorname{OPT}_{\mathrm{fluid}}(I)>0\) as the maximum total unadjusted reward over all feasible fractional histories, without stagewise optimality restrictions. The threshold \(\rho\in[0,1]\) is binary rational; \(L\) is total input bit length. State running times in \(m,\tau,L,H,\ell,d\).
Is deciding whether there exists \(p\in\mathbb R^B\) with \(\operatorname{VAL}_V(I,p)\ge\rho\operatorname{OPT}_{\mathrm{fluid}}(I)\) in P or NP-hard?
For every \(k\ge1\), do two-stage fluid instances retain the vertex-potential upper-bound examples with ratios \((4k+4)/(6k+4)\), \((4k+5)/(6k+5)\), and \(5/6\), respectively for cycles capped at \(2k+4\) without chains, cycles capped at \(2\) with chains capped at \(2k+5\), and cycles capped at \(2\) without chains, when every role mass is multiplied by \(M\to\infty\); or does fractional matching invalidate one or more bounds?
Discrete two-stage instances have the three stated vertex-potential upper bounds, while edge potentials attain the omniscient optimum on those instances. [Dickerson, Procaccia, and Sandholm, 2012](https://www.cs.cmu.edu/~sandholm/www/dynamicMatchingViaWeightedMyopia.aaai12.pdf).
No result settling this precise fluid model with fixed ABO vertex potentials and adversarial tie-breaking was located in the literature search.
All three requested upper-bound ratios survive fractional clearing, exactly and at every positive rational mass scale.
For the complexity question, the results proved below are:
These results exclude polynomial-time solvability unless $\mathrm P=\mathrm{NP}$. They establish $\mathrm{NP}$-hardness under polynomial-time Turing reductions, but do not establish $\mathrm{NP}$-hardness under polynomial-time many-one reductions. That part of the requested classification remains unresolved.
Throughout, support size means the number $\tau$ of listed complete role types. No enumeration of possible role types is used. Put
$$ C=\max\{2,\ell,d\}. $$
For $H=1$, or for $\rho=0$, the decision answer is immediately yes. The arguments below concern the remaining cases.
For every template $c$,
$$ w_c=\sum_s a_{s,c}. $$
For a cycle, both sides count its pair roles. For a chain with $t$ pairs, the right side counts those pairs and its altruist, while the reward is $t+1$, including the waiting-list transplant.
Consequently, every feasible history satisfies
$$ \sum_{r,c}w_cy_c^r = \sum_s\sum_{r,c}a_{s,c}y_c^r \leq \sum_s q_s. $$
The last inequality follows from permanent consumption and the capacity constraint for each role. Thus losing $a$ units of role mass implies losing at least $a$ units relative to the total-mass upper bound.
Let $MI$ be obtained by multiplying all masses by a positive rational $M$. The correspondence
$$ y_c^r\longmapsto My_c^r $$
is a bijection between feasible histories of $I$ and $MI$. Residual capacities and every stage objective are multiplied by $M$. Hence it preserves stagewise maximization, including ties, in both directions.
Taking the adversarial infimum therefore gives, for every fixed $p$,
$$ \operatorname{VAL}_V(MI,p)=M\operatorname{VAL}_V(I,p), $$
and unrestricted optimization gives
$$ \operatorname{OPT}_{\mathrm{fluid}}(MI) = M\operatorname{OPT}_{\mathrm{fluid}}(I). $$
Every ratio is consequently unchanged. In particular, scaling introduces no asymptotic approximation: the examples below work for every positive integer $M$, and hence as $M\to\infty$.
The common availability interval of a template $c$ is nonempty exactly when
$$ \max_{s:a_{s,c}>0}\alpha_s \leq \min_{s:a_{s,c}>0}\beta_s. $$
Discard templates failing this test. The benchmark is the value of
$$ \max_{x\geq0} \left\{ \sum_c w_cx_c: \sum_c a_{s,c}x_c\leq q_s\quad\text{for every }s \right\}. $$
To prove this, first aggregate any feasible history by setting $x_c=\sum_r y_c^r$. Permanent consumption gives all the displayed capacity inequalities.
Conversely, take any feasible $x$ and schedule each template’s entire flow at one stage in its common availability interval. For every role, consumption through any stage is at most its total scheduled consumption, which is at most $q_s$. All scheduled roles are present when used. The resulting history is therefore feasible and has the same reward.
The benchmark is computable in time
$$ \operatorname{poly}(m,\tau,L,\log H,\log C). $$
This includes checking availability and solving the explicit rational linear program.
Each vertex used below is a separate complete role type of mass $1$. The listed arcs are the entire typed compatibility relation. All permitted templates under the stated caps are included.
Write patient ABO type first, and define
$$ X=\mathrm{AB}\!-\!\mathrm O,\qquad Y=\mathrm{AB}\!-\!\mathrm A,\qquad Z=\mathrm A\!-\!\mathrm A,\qquad W=\mathrm A\!-\!\mathrm O. $$
The following four adjusted two-cycle rewards will be used:
$$ h_1=2-p_X-p_Y,\qquad h_2=2-p_Z-p_W, $$
$$ g_1=2-p_X-p_W,\qquad g_2=2-p_Y-p_Z. $$
They satisfy the exact identity
$$ h_1+h_2=g_1+g_2. $$
The first two graph patterns are those underlying the stated discrete bounds in [Dickerson, Procaccia, and Sandholm](https://www.cs.cmu.edu/~sandholm/www/dynamicMatchingViaWeightedMyopia.aaai12.pdf). The arguments here establish their fluid behavior directly.
Fix $k\geq1$. Create four persistent roles $x,y,z,w$, of types $X,Y,Z,W$, present at both stages. Their arcs are
$$ x\leftrightarrow y,\qquad z\leftrightarrow w,\qquad y\to z. $$
At stage $1$, also include $k$ disjoint, expiring two-cycles with ABO types $X,W$, and $k$ disjoint, expiring two-cycles with ABO types $Y,Z$.
At stage $2$, introduce $2k$ new roles $u_1,\ldots,u_{2k}$, all of type $\mathrm{AB}\!-\!\mathrm{AB}$, and add
$$ w\to u_1\to u_2\to\cdots\to u_{2k}\to x. $$
Every arc respects ABO compatibility. For example, $y\to z$ is an $\mathrm A$ donor donating to an $\mathrm A$ patient, and $u_{2k}\to x$ is an $\mathrm{AB}$ donor donating to an $\mathrm{AB}$ patient.
The long cycle is
$$ x\to y\to z\to w\to u_1\to\cdots\to u_{2k}\to x, $$
of length $2k+4$.
Benchmark. Clearing all expiring cycles first and the long cycle second consumes every role. The total mass is $6k+4$, so Section 1.1 proves
$$ \operatorname{OPT}_{\mathrm{fluid}}(I)=6k+4. $$
Upper bound for every potential. Fix $p$.
If $h_1\geq0$ or $h_2\geq0$, adversarial clearing can saturate the corresponding persistent two-cycle at stage $1$. This is consistent with maximization: the available cycles belong to independent two-cycle components, and the one-way arc $y\to z$ creates no additional stage-$1$ cycle.
Saturation consumes either $x,y$ or $z,w$. Every stage-$2$ template containing a new role requires all four persistent roles, so none of the $2k$ new roles can then be consumed. Total reward is at most
$$ (6k+4)-2k=4k+4. $$
If both $h_1<0$ and $h_2<0$, then $g_1+g_2<0$, so at least one of $g_1,g_2$ is negative. Every maximizing first-stage flow leaves the corresponding independent expiring family unused. That loses $2k$ units of mass and again gives the same upper bound.
Thus
$$ \operatorname{VAL}_V(I,p)\leq4k+4 \quad\text{for every }p. $$
At $p=0$, first-stage maximization consumes all $4k+4$ units of mass present at stage $1$. The long cycle is then blocked, so every maximizing history has total reward $4k+4$. Therefore
$$ \max_p \frac{\operatorname{VAL}_V(I,p)} {\operatorname{OPT}_{\mathrm{fluid}}(I)} = \frac{4k+4}{6k+4}. $$
If repeated role occurrences are permitted, repeating an independent two-cycle merely multiplies its consumption and adjusted reward by the same factor. A closed walk containing a new role has length at least $2k+4$; under the cap it must be the displayed long cycle. The proof therefore covers that convention as well.
Use the preceding construction, but delete $u_{2k}\to x$. Introduce a stage-$2$ altruist $a$ of donor type $\mathrm O$, with arc $a\to x$. Allow only two-cycles, and set the chain cap to $2k+5$.
The full chain is
$$ a\to x\to y\to z\to w\to u_1\to\cdots\to u_{2k} \to\text{waiting list}. $$
It contains $2k+4$ pairs and has reward $2k+5$. Include every admissible terminating prefix.
Benchmark. Expiring cycles at stage $1$ followed by the full chain consume all $6k+5$ units of mass. Hence
$$ \operatorname{OPT}_{\mathrm{fluid}}(I)=6k+5. $$
Upper bound. If either $h_i$ is nonnegative, the adversary can saturate its persistent two-cycle first. Every chain reaching any $u_j$ must traverse $x,y,z,w$. Thus none of the $2k$ new pair roles can be consumed. Chain prefixes may still consume other roles, but Section 1.1 bounds total reward by $4k+5$.
If both $h_i$ are negative, the identity forces an expiring family to have negative adjusted reward. Losing its $2k$ units gives the same bound. Therefore
$$ \operatorname{VAL}_V(I,p)\leq4k+5 \quad\text{for every }p. $$
Attainment. Choose
$$ p_X=0,\qquad p_Y=3,\qquad p_Z=-2,\qquad p_W=1. $$
Then
$$ h_1=-1,\qquad h_2=3,\qquad g_1=g_2=1. $$
Every first-stage maximizer consumes both expiring families and the persistent $z,w$ cycle, obtaining reward $4k+2$, while preserving $x,y$.
At stage $2$, the terminating prefix through $a,x,y$ consumes all three reachable remaining roles and gives reward $3$. No chain can pass the exhausted role $z$, and the new roles have no other way to be consumed. Consequently,
$$ \max_p \frac{\operatorname{VAL}_V(I,p)} {\operatorname{OPT}_{\mathrm{fluid}}(I)} = \frac{4k+5}{6k+5}. $$
Repeated prefixes, if permitted, cannot increase the final reward beyond the mass of the three reachable roles.
Create persistent roles $x,y,z,w$ of types $X,Y,Z,W$, and stage-$1$ cycles $x\leftrightarrow y$ and $z\leftrightarrow w$.
Also create one disjoint, expiring $X,W$ two-cycle and one disjoint, expiring $Y,Z$ two-cycle.
At stage $2$, introduce four new roles, each adjacent in both directions only to its corresponding persistent role:
| Persistent role | New partner’s ABO type |
|---|---|
| $x$ | $\mathrm{AB}\!-\!\mathrm{AB}$ |
| $y$ | $\mathrm A\!-\!\mathrm{AB}$ |
| $z$ | $\mathrm A\!-\!\mathrm A$ |
| $w$ | $\mathrm O\!-\!\mathrm A$ |
Each private two-cycle respects ABO compatibility. For the last row, for example, $w$’s $\mathrm O$ donor can donate to its partner’s $\mathrm O$ patient, while the partner’s $\mathrm A$ donor can donate to $w$’s $\mathrm A$ patient.
The cap is $2$, and there are no chains.
Benchmark. Clearing the two expiring cycles first and the four private persistent–new cycles second consumes all $12$ units:
$$ \operatorname{OPT}_{\mathrm{fluid}}(I)=12. $$
If either $h_i$ is nonnegative, the adversary can consume its persistent two-cycle first. Its two private arriving partners are then unusable, so total reward is at most $10$.
If both $h_i$ are negative, one expiring two-cycle has negative coefficient and remains unused, again giving total reward at most $10$.
The potentials from Section 2.2 force both expiring cycles and $z,w$ to clear first, giving reward $6$. At stage $2$, $x,y$ clear with their private partners, giving reward $4$. Thus
$$ \max_p \frac{\operatorname{VAL}_V(I,p)} {\operatorname{OPT}_{\mathrm{fluid}}(I)} = \frac{10}{12} = \frac56. $$
This fixed example applies for every $k\geq1$, since the third requested cap does not depend on $k$.
The three supports have sizes $6k+4$, $6k+5$, and $12$, respectively.
Their complete template lists have polynomial size in $k$. Under a convention allowing repetitions, the cycle example adds only repetitions of independent two-cycles. In the chain example, a path can bounce within $x,y$, then within $z,w$, before proceeding along the new-role path. The two bounce counts and the terminating position determine the template, giving $O(k^3)$ possibilities.
Section 1.2 proves that all three exact ratios persist under uniform mass multiplication.
Use the NP-complete threshold version of Maximum Cut on nonempty simple cubic graphs. The restricted hardness is established by [Alimonti and Kann](https://www.cs.yale.edu/homes/aspnes/pinewiki/attachments/MarkovChains/alimanti-mis-cubic.pdf).
Let $G=(V,E)$ have
$$ n=|V|,\qquad e=|E|=\frac{3n}{2}, $$
and let $\kappa(G)$ denote its maximum cut size. The source threshold is $1\leq K\leq e$.
Every constructed role has unit mass and ABO type $\mathrm O\!-\!\mathrm O$. Consequently, every specified arc is ABO-compatible. Set $H=2$, forbid chains, and set $\ell=6$.
For each vertex $v$, order its three incident edges as $f_1,f_2,f_3$. Create one stage-$1$-only hub $h_v$. For each $\varepsilon\in\{0,1\}$, create three persistent roles $t_{v,f_i}^{\varepsilon}$ and two stage-$1$-only blockers $b_{v,1}^{\varepsilon},b_{v,2}^{\varepsilon}$. Add
$$ h_v\to t_{v,f_1}^{\varepsilon}\to b_{v,1}^{\varepsilon} \to t_{v,f_2}^{\varepsilon}\to b_{v,2}^{\varepsilon} \to t_{v,f_3}^{\varepsilon}\to h_v. $$
These two six-cycles share only their hub. Their first-stage flows satisfy precisely
$$ x_v^0\geq0,\qquad x_v^1\geq0,\qquad x_v^0+x_v^1\leq1. $$
Totally order $V$. For each edge $f=\{u,v\}$ with $u<v$, and each $\varepsilon$, create a stage-$2$-only role $z_f^\varepsilon$ and add the triangle
$$ t_{u,f}^{\varepsilon}\to z_f^\varepsilon \to t_{v,f}^{\varepsilon}\to t_{u,f}^{\varepsilon}. $$
At stage $1$, every available inter-variable arc strictly decreases the vertex order. Such arcs cannot belong to a cycle traversing distinct variable components. Within a variable component, switching between its two branches would require a walk of length at least $12$. Therefore the cap-$6$ first-stage possibilities are exactly the two specified local cycles.
At stage $2$, hubs and blockers have expired. The remaining triangles are disjoint: each persistent endpoint role is indexed by one incident edge and one value of $\varepsilon$.
Finally, add $3e$ isolated, stage-$1$-only two-cycles. Their total reward is
$$ R=6e. $$
There are $11n$ variable-component roles, $2e=3n$ triangle roles, and $6e=9n$ isolated-cycle roles. Thus
$$ \tau=23n. $$
All templates can be listed by checking directed sequences of length at most $6$, requiring $O(\tau^6)$ candidate checks. The reduction has polynomial size. Repeated two-cycles or twice-traversed triangles, if allowed, merely duplicate their ordinary aggregate-flow possibilities.
Put
$$ t_v=x_v^0+x_v^1,\qquad 0\leq t_v\leq1. $$
Variable cycles contribute $6\sum_v t_v$. For an edge $\{u,v\}$, its triangles contribute at most
$$ 3\sum_{\varepsilon\in\{0,1\}} \min\{1-x_u^\varepsilon,1-x_v^\varepsilon\} \leq 3\left(2-\frac{t_u+t_v}{2}\right). $$
The inequality applies $\min\{a,b\}\leq(a+b)/2$ separately to the two terms.
Since the graph is cubic,
$$ \sum_{\{u,v\}\in E}(t_u+t_v)=3\sum_v t_v. $$
Every history therefore has reward at most
$$ R+6\sum_v t_v+6e-\frac92\sum_v t_v = R+6e+\frac32\sum_v t_v \leq R+7e. $$
Equality is feasible: clear every isolated cycle; use $x_v^0=x_v^1=1/2$ for every vertex; and clear every final triangle with flow $1/2$. Hence
$$ \operatorname{OPT}_{\mathrm{fluid}}(I)=R+7e=13e. $$
Let $p_0$ be the potential on $\mathrm O\!-\!\mathrm O$. Every early template has coefficient $w_c(1-p_0)$.
For $p_0<1$, early maximization is unadjusted reward maximization. It clears all isolated cycles and forces $t_v=1$ for every variable component. Write $x_v=x_v^0$, so $x_v^1=1-x_v$.
The final reward of an edge is exactly
$$ 3\bigl( \min\{1-x_u,1-x_v\} + \min\{x_u,x_v\} \bigr) = 3(1-|x_u-x_v|). $$
The equality follows by considering $x_u\leq x_v$ and $x_v\leq x_u$. Disjointness of the triangles makes their individual capacity bounds simultaneously attainable.
Using $6n=4e$, total reward is therefore
$$ R+7e-3\sum_{\{u,v\}\in E}|x_u-x_v|. $$
For every $x\in[0,1]^V$, define $S_t=\{v:x_v>t\}$. An edge’s endpoints lie on opposite sides for a set of thresholds of length $|x_u-x_v|$. Thus
$$ \sum_{\{u,v\}\in E}|x_u-x_v| = \int_0^1|\delta(S_t)|\,dt \leq \kappa(G). $$
A binary characteristic vector of a maximum cut attains equality. Consequently,
$$ \operatorname{VAL}_V(I,p)=13e-3\kappa(G) \qquad\text{when }p_0<1. $$
For $p_0>1$, every nonempty early clearing has negative adjusted reward. Empty clearing is uniquely optimal, and the final stage clears all $2e$ triangles with unit flow, giving $6e$.
For $p_0=1$, empty early clearing is an adversarially available maximizer, so the value is at most $6e$.
Since $\kappa(G)\leq e$,
$$ 13e-3\kappa(G)\geq10e>6e. $$
It follows that
$$ \max_p\operatorname{VAL}_V(I,p)=13e-3\kappa(G). $$
To accommodate even an interpretation requiring a finite binary expansion, choose a dyadic threshold. Put
$$ \theta=13e-3(K-1),\qquad Q=2^{\lceil\log_2(13e)\rceil}, $$
and set
$$ \rho= \frac{\left\lfloor Q\theta/(13e)\right\rfloor}{Q}. $$
This lies in $[0,1]$ and has polynomial bit length. Moreover,
$$ \theta-3<\rho\,13e\leq\theta, $$
because rounding down changes $\theta$ by less than $13e/Q\leq1$.
The exact value formula now gives
$$ \exists p:\operatorname{VAL}_V(I,p) \geq\rho\operatorname{OPT}_{\mathrm{fluid}}(I) \quad\Longleftrightarrow\quad \kappa(G)\leq K-1. $$
Indeed, if $\kappa(G)\leq K-1$, the best value is at least $\theta$. If $\kappa(G)\geq K$, it is at most $\theta-3$, strictly below the chosen threshold.
This is a polynomial-time many-one reduction from the complement of cubic Maximum Cut. It proves $\mathrm{coNP}$-hardness, with the restrictions stated above.
Partition the pre-final stages into maximal intervals with constant active-role sets. There are at most $2\tau+1$ such intervals. Keep the final stage separate, and write
$$ h\leq\min\{H,2\tau+2\} $$
for the resulting number of stages.
Consider one constant-availability interval. Let its first maximizing clearing have adjusted value $v$. Any later feasible clearing can be added to it: together they consume no more than the residual mass at the interval’s start.
No later clearing can have positive adjusted value, since adding it would contradict the first clearing’s optimality. Every later maximizing clearing therefore has adjusted value zero, because empty clearing is feasible.
Aggregating the interval’s clearings into its first stage preserves feasibility, optimality, total reward, and the residual state at the interval’s end. Conversely, after that aggregated maximizing clearing, empty clearing is optimal throughout the remaining interval.
Thus compression preserves all attainable adversarial total rewards. It is computable by sorting the binary arrival and expiration events.
Fix rational $p$. At a stage, let $A$ be the available-template capacity matrix, $b$ the residual-capacity vector, and $f(p)$ the adjusted reward vector. The primal and dual are
$$ \max\{f(p)^{\mathsf T}y:Ay\leq b,\ y\geq0\}, $$
$$ \min\{b^{\mathsf T}\lambda: A^{\mathsf T}\lambda\geq f(p),\ \lambda\geq0\}. $$
The primal is nonempty because $y=0$ is feasible. It is bounded because each template consumes some positive amount of a finite-mass role. Linear-programming strong duality therefore applies.
Optimality is equivalent to primal and dual feasibility and
$$ y_c\bigl((A^{\mathsf T}\lambda)_c-f_c(p)\bigr)=0, $$
$$ \lambda_s\bigl(b_s-(Ay)_s\bigr)=0. $$
At the final stage replace $f(p)$ by $w$.
For each product, select one factor to equal zero. There are at most
$$ 2^{h(m+\tau)} $$
choices across the compressed horizon. After fixing a choice, every constraint is linear: each residual capacity is an affine function of earlier flows.
Minimize total reward on each feasible branch and take the smallest value. This computes $\operatorname{VAL}_V(I,p)$ in time
$$ 2^{h(m+\tau)} \operatorname{poly} \bigl(m,\tau,h,L,\operatorname{bits}(p),\log C\bigr). $$
For fixed $p$, each branch is a polyhedron. Its projection onto flow histories is also a polyhedron. These projections form a finite union, and all flow coordinates are bounded by initial masses. Hence the set of maximizing histories is compact, and the adversarial infimum is attained.
We use the following elementary rational-polyhedron fact.
Fact. Let a polyhedron in $n$ variables have rational constraint entries of at most $B$ bits. Each vertex has coordinate numerator and denominator lengths
$$ O(n^2B+n\log n). $$
To see this, a vertex is determined by $n$ independent active constraints. Clearing denominators separately in those rows gives integer entries of $O(nB)$ bits. Cramer’s rule and the determinant bound then give the stated estimate.
A nonempty polyhedron contained in the nonnegative orthant, on which a linear objective attains its minimum, has an optimal vertex. For completeness, minimize the sum of coordinates on its optimal face. A sublevel set bounded by the sum at any fixed feasible point is compact. The resulting minimum face is a nonempty polytope and has an extreme point. Since it is a face of a face of the original polyhedron, that point is a vertex of the original polyhedron.
These observations apply to each complementary-slackness branch: all flow and dual variables are nonnegative, and the reward minimum is attained by the projection argument above. A minimizing branch consequently has a rational solution of polynomial bit length.
Therefore, if
$$ \operatorname{VAL}_V(I,p)<T, $$
polynomial-length rational flows and dual variables certify a maximizing history whose total reward is below $T$. Exact rational arithmetic verifies feasibility, complementary slackness, and the strict reward inequality in polynomial time.
The threshold test for a supplied rational potential thus belongs to $\mathrm{coNP}$.
This section strengthens the rational-witness argument and handles strict inequalities and lineality explicitly.
Let $b_0=|B|=20$, and reparameterize potentials by
$$ u_b=1-p_b. $$
For a stage matrix $A$, define the grouped-consumption matrix $D$ by
$$ D_{b,c}=\sum_{s:g(s)=b}a_{s,c}. $$
Section 1.1 gives
$$ f(p)=D^{\mathsf T}u. $$
In particular, all pre-final objectives are homogeneous in $u$.
For a feasible stage flow $y$, let $T$ be its set of tight capacity rows, and let $Z$ be its set of zero-flow coordinates. Complementary slackness says that $y$ is maximizing exactly when $u$ belongs to
$$ \begin{aligned} K_{T,Z}=\{u:\ &\exists\lambda\geq0,\quad \lambda_s=0\ \text{for }s\notin T,\\ &A^{\mathsf T}\lambda\geq D^{\mathsf T}u,\\ &(A^{\mathsf T}\lambda)_c=(D^{\mathsf T}u)_c \ \text{for }c\notin Z\}. \end{aligned} $$
Crucially, this cone depends on $A,D,T,Z$, and not on residual capacities. Over all compressed pre-final stages, there are at most
$$ h\,2^{m+\tau} $$
such cones.
Remove dual variables outside $T$ and write the remaining system as
$$ F\lambda\geq Eu. $$
Here $\lambda$ is unrestricted in this notation, with its nonnegativity included as rows of $F$. Equalities are represented by both signs. There are at most $2m+\tau$ rows, at most $\tau$ columns in $F$, and all entries of $F,E$ are integers of absolute value at most $C$.
Farkas’ lemma gives
$$ u\in K_{T,Z} \quad\Longleftrightarrow\quad v^{\mathsf T}Eu\leq0 \quad\text{for every }v\geq0\text{ with }F^{\mathsf T}v=0. $$
It suffices to test extreme rays of the cone
$$ \{v\geq0:F^{\mathsf T}v=0\}. $$
Such a ray has support size at most $\tau+1$. Indeed, if its support has size $j$ and the restricted nullspace has dimension at least two, there is a nonproportional nullspace direction supported there. Small perturbations in both signs remain nonnegative, contradicting extremality. Thus the restricted matrix has rank $j-1$, and $j-1\leq\tau$.
Cofactors of $j-1$ independent rows supply an integer generator for the ray, with coordinates bounded by
$$ \tau!C^\tau. $$
The resulting normal vector $-E^{\mathsf T}v$ has coordinates bounded by
$$ U=(\tau+1)C\,\tau!C^\tau. $$
Hence every $K_{T,Z}$ is an intersection of homogeneous integer halfspaces whose coefficient bit length is at most
$$ D_*=\left\lceil\log_2(1+U)\right\rceil = O\bigl((\tau+1)\log((\tau+1)C)\bigr). $$
This also proves that each cone is closed. The description handles lower-dimensional cones: opposing inequalities can enforce their defining equalities.
The number of candidate extreme-ray supports is at most $(2m+\tau+1)^{\tau+1}$. Thus all nonzero boundary normals can be listed with total count bounded by
$$ N= h\,2^{m+\tau}(2m+\tau+1)^{\tau+1}. $$
Fix $u_0$. Every cone not containing $u_0$ is closed, so some neighborhood of $u_0$ avoids it. There are finitely many cones, so one neighborhood avoids all such cones simultaneously.
For every $u$ in this neighborhood,
$$ u\in K_{T,Z}\quad\Longrightarrow\quad u_0\in K_{T,Z}. $$
It follows that every stage flow maximizing at $u$ also maximizes at $u_0$, for every feasible residual-capacity vector. Applying this to successive stages gives inclusion of the entire history sets. The final objective is unchanged. Consequently,
$$ \operatorname{VAL}_V(I,\mathbf1-u) \geq \operatorname{VAL}_V(I,\mathbf1-u_0) $$
throughout that neighborhood.
The finitely many nonzero boundary hyperplanes cannot cover an open neighborhood. We can therefore perturb $u_0$ into a full-dimensional chamber while preserving any successful threshold guarantee.
Inside a chamber, every boundary-normal sign is fixed. Membership in every optimality cone is therefore fixed, so the complete set of maximizing histories—and its adversarial value—is constant throughout that chamber.
A chamber has a description
$$ \sigma_i n_i^{\mathsf T}u>0, $$
where $\sigma_i\in\{-1,1\}$ and every $n_i$ is integral with coordinates bounded by $U$.
By positive scaling, feasibility is equivalent to
$$ \sigma_i n_i^{\mathsf T}u\geq1 \quad\text{for every }i. $$
Write $u=u^+-u^-$ with $u^+,u^-\geq0$, and minimize
$$ \sum_b(u_b^++u_b^-) $$
subject to these inequalities. This LP has $2b_0=40$ variables. It is feasible, and its objective has compact sublevel sets, so it has an optimal vertex.
That vertex is determined by $40$ independent active constraints with integer coefficients bounded by $U$ and right sides in $\{0,1\}$. Cramer’s rule supplies a common denominator $\Delta$ and coordinate numerators, all bounded in absolute value by
$$ 40!\,U^{40}. $$
Multiplying $u$ by the positive integer $\Delta$ therefore produces an integer vector in the same chamber. Each coordinate has bit length
$$ O(D_*)= O\bigl((\tau+1)\log((\tau+1)C)\bigr), $$
where the constant uses the fixed value $b_0=20$.
Positive scaling of $u$ multiplies every pre-final objective by the same positive number, preserving its maximizers. Thus the integer vector gives exactly the same histories.
We have proved:
Integer-potential theorem. If any real $p$ satisfies the requested threshold, an integer $p$ satisfies it, with each coordinate having
$$ O\bigl((\tau+1)\log((\tau+1)C)\bigr) $$
bits. A successful potential can be chosen in a full-dimensional chamber.
This proof requires no vertex in an unrestricted polyhedron: splitting coordinates and minimizing their sum removes the lineality issue.
The integer-potential theorem supplies a polynomial-length existential witness. Section 4.3 supplies an NP certificate for failure of that witness. Therefore the general decision problem belongs to
$$ \Sigma_2^p. $$
There is also an explicit deterministic algorithm. Enumerate the cone normals, enumerate the full-dimensional chambers of their arrangement in $\mathbb R^{20}$, choose an integer representative of each chamber, and evaluate it by Section 4.2.
An arrangement of $N$ hyperplanes in fixed dimension $20$ has $N^{O(20)}$ chambers. They can be constructed incrementally: intersect each existing chamber with the two strict signs of the next hyperplane, testing feasibility by the homogeneous normalization used above. Only nonempty chambers are retained.
Combining this enumeration with complementary-slackness branching gives running time
$$ 2^{\,O\left(h(m+\tau)+\tau\log(2m+\tau+1)\right)} \operatorname{poly}(m,\tau,h,L,\log C), $$
where
$$ h\leq\min\{H,2\tau+2\}. $$
The constants in the exponential use the fixed number of ABO potential coordinates.
Consider cycle-only instances whose roles all have the same patient–donor ABO type. Let its common potential be $p_0$.
There are only three relevant regimes:
Therefore
$$ \max_p\operatorname{VAL}_V(I,p)=\max\{G_I,W_I\}. $$
The value $W_I$ is computable by the final-stage reward LP. Failure of the threshold test means
$$ W_I<T \quad\text{and}\quad G_I<T. $$
The first inequality is decidable in polynomial time. The second has the polynomial certificate from Section 4.3, using $p_0=0$. The complement of the restricted decision problem is consequently in NP.
Section 3 proves hardness already within this class, with $H=2$, unit masses, and $\ell=6$. Hence the restricted problem is $\mathrm{coNP}$-complete. Its coNP membership holds for arbitrary horizons and cycle caps.
The fluid scaling question is settled: the three exact best-potential ratios are
$$ \frac{4k+4}{6k+4},\qquad \frac{4k+5}{6k+5},\qquad \frac56, $$
and remain unchanged after uniform mass multiplication.
For the general decision problem, the proved classification is $\mathrm{coNP}$-hardness and membership in $\Sigma_2^p$. The lower bound rules out a polynomial-time algorithm unless $\mathrm P=\mathrm{NP}$.
Negating the answer to the instance constructed in Section 3 decides cubic Maximum Cut with one oracle query. This establishes polynomial-time Turing $\mathrm{NP}$-hardness. It does not supply a many-one reduction preserving NP-source yes answers. No such reduction, or complete alternative classification, is proved here.
⟨structured verdict parsed — rendered above⟩
The output provides substantial, correct partial results. The three fluid upper-bound examples are verified, and the complexity arguments establish $\mathrm{coNP}$-hardness, membership in $\Sigma_2^p$, and $\mathrm{coNP}$-completeness for the stated restricted class. It does not settle the requested general classification under the usual interpretation of $\mathrm{NP}$-hardness as polynomial-time many-one hardness. The prover explicitly acknowledges this limitation.
I found no central false step in the mathematical arguments presented.
The identity
$$
w_c=\sum_s a_{s,c}
$$
holds under the task’s chain convention: the altruist and the pair roles together number exactly the rewarded transplants, including the final waiting-list donation. The waiting list consumes no additional role mass.
Permanent consumption consequently gives the stated total-mass upper bound. Its later applications are valid because each example’s unrestricted benchmark consumes every role.
Uniform multiplication of masses by a positive rational gives a bijection of feasible histories, preserves every stage’s maximizing flows, and scales total reward. This includes adversarial ties. Therefore both $\operatorname{VAL}_V$ and $\operatorname{OPT}_{\mathrm{fluid}}$ scale exactly.
The benchmark LP is also correct. Aggregating histories gives its capacity constraints; scheduling each template within its common availability interval preserves feasibility because cumulative consumption never exceeds total allocated consumption. The stated polynomial running time uses the explicitly listed templates and does not enumerate possible role types.
The initial cases $H=1$ and $\rho=0$ are correctly handled.
All specified arcs respect ABO compatibility. At the first stage, the available cycle components are independent, despite the one-way arc between the persistent components.
If either persistent cycle has nonnegative adjusted reward, fully saturating it is an available maximizing choice. This remains true when its coefficient is zero, which is precisely where adversarial tie-breaking matters. Saturation prevents consumption of every newly arriving role.
If both persistent-cycle coefficients are negative, the identity
$$
h_1+h_2=g_1+g_2
$$
forces an entire expiring family to have negative adjusted reward. Its independent flows must then be zero in every maximizing clearing.
Both cases lose at least $2k$ units from the attainable total mass $6k+4$. The choice $p=0$ attains reward $4k+4$ under every maximizing history. Thus the claimed exact best-potential ratio is established.
The discussion of repeated role occurrences is consistent with the proof: repetitions of a two-cycle give proportional consumption and objective columns, and the cap prevents a longer walk containing a new role.
The full chain contains $2k+4$ pairs, so its reward and capped length are both $2k+5$, as required by the task. Including terminating prefixes does not invalidate the upper bound: every chain reaching a new role must traverse all four persistent roles.
The specified potentials give exactly
$$
(h_1,h_2,g_1,g_2)=(-1,3,1,1).
$$
Hence the first stage consumes both expiring families and the persistent $z,w$ cycle, earning $4k+2$. At the final stage, the prefix through $a,x,y$ earns $3$, and the exhausted role $z$ blocks access to the new roles.
Fractional or repeated prefixes cannot earn more than the mass of the three remaining reachable roles. The exact ratio
$$
\frac{4k+5}{6k+5}
$$
follows.
Every private persistent–new two-cycle is ABO-compatible, including the partners whose patient and donor blood types differ.
The benchmark consumes all $12$ units. Saturating either persistent first-stage cycle makes its two new partners unusable. Alternatively, negative coefficients on both persistent cycles force one expiring cycle to remain unused. Each case limits total reward to $10$.
The supplied potentials attain first-stage reward $6$ and final-stage reward $4$. Therefore the exact ratio is $\frac56$.
These arguments establish that all three bounds survive fluid clearing at every positive rational scale. The cited discrete paper states the same caps and ratios; the fluid conclusions here are supported by the prover’s direct arguments, rather than inferred from the discrete theorem. [Dickerson, Procaccia, and Sandholm](https://www.cs.cmu.edu/~sandholm/www/dynamicMatchingViaWeightedMyopia.aaai12.pdf)
The source restriction is appropriate. The cited paper establishes Maximum Cut hardness for simple graphs of maximum degree three and explicitly extends it to graphs of degree exactly three. Thus the reduction’s use of
$$
e=\frac{3n}{2}
$$
is justified. [Alimonti and Kann](https://www.cs.yale.edu/homes/aspnes/pinewiki/attachments/MarkovChains/alimanti-mis-cubic.pdf)
The constructed arcs are ABO-compatible because every pair has type $\mathrm O\!-\!\mathrm O$. At the first stage, inter-component arcs strictly decrease the vertex order, preventing cycles through distinct variable components. Within each component, the two six-cycles share only the hub, giving exactly the displayed aggregate constraints.
At the second stage, expired hubs and blockers remove the local branches, and the edge/value-indexed triangles are disjoint. The support count $\tau=23n$ is correct, and enumerating capped templates has polynomial cost.
The benchmark calculation is correct:
$$
\operatorname{OPT}_{\mathrm{fluid}}(I)=13e.
$$
The upper bound uses the cubic incidence identity correctly, and the half-and-half assignment attains it.
For $p_0<1$, the first-stage maximizing constraints force each variable’s aggregate cycle flow to equal $1$. The final edge reward is correctly calculated as
$$
3(1-|x_u-x_v|).
$$
The threshold-integral identity establishes that the largest possible sum of these absolute differences equals the maximum cut size. Binary cut vectors attain the bound, so fractional assignments introduce no discrepancy.
The other potential regimes are handled correctly. Therefore
$$
\max_p\operatorname{VAL}_V(I,p)=13e-3\kappa(G)
$$
is established.
The dyadic threshold calculation preserves the required strict separation: the rounding loss is less than $1$, whereas consecutive cut values differ by $3$ in the constructed reward.
The proved equivalence is
$$
\exists p:\operatorname{VAL}_V(I,p)
\geq\rho\operatorname{OPT}_{\mathrm{fluid}}(I)
\quad\Longleftrightarrow\quad
\kappa(G)\leq K-1.
$$
This maps yes instances of the complement of the Maximum Cut threshold problem to yes instances of the target. It proves polynomial-time many-one $\mathrm{coNP}$-hardness.
Negating the target oracle’s answer gives a valid polynomial-time Turing reduction for Maximum Cut. It does not give a many-one $\mathrm{NP}$-hardness reduction.
Major scope issue: the general $\mathrm P$ versus many-one $\mathrm{NP}$-hardness question remains unsettled. This is an acknowledged incompleteness, not an error in the reduction.
Minimum additional work: supply the missing many-one hardness argument or a polynomial-time algorithm for the general target. Rewording the existing reduction cannot supply either result.
Within a constant-availability interval, later feasible consumption can be added to the first clearing. A later clearing with positive adjusted value would contradict the first clearing’s optimality. Since empty clearing is feasible, all subsequent maximizing clearings have adjusted value zero.
Aggregation therefore preserves optimality, interval-end residual capacities, and total unadjusted reward. The reverse expansion using empty clearings is valid. Keeping the final stage separate is essential and is done explicitly.
The primal and dual LPs have the correct signs and domains. Feasibility and boundedness justify strong duality and the stated complementary-slackness conditions.
Selecting a zero factor in every complementary-slackness product produces linear branches because residual capacities are affine in earlier flows. The branch count and fixed-potential running time are valid.
The compactness argument correctly uses projections of polyhedra and bounded flow coordinates; it does not incorrectly assume that dual variables are bounded. The subsequent rational-vertex argument supplies polynomial-length certificates of strict threshold failure. Thus the supplied-rational-potential test belongs to $\mathrm{coNP}$.
The reparameterization
$$
u_b=1-p_b
$$
correctly makes every early-stage objective homogeneous. The optimality cone for a feasible flow depends on its tight capacity rows and zero-flow coordinates, rather than on the numerical residual capacities.
The Farkas formulation has the correct inequality direction. Its multiplier cone is pointed because it lies in the nonnegative orthant, so testing extreme rays suffices. The support-size argument and cofactor bounds justify the stated integer normal bounds.
Closedness and finiteness of the cones justify the neighborhood argument: a sufficiently small perturbation cannot introduce an optimality pattern absent at the original potential. Consequently, it cannot introduce a new maximizing history, and the adversarial value cannot decrease.
Chamber membership fixes every cone-membership decision. The normalized chamber inequalities and coordinate-splitting LP therefore yield an integer representative of polynomial bit length. Structural ties may remain; the argument establishes avoidance of the listed nonzero boundary hyperplanes, not uniqueness of clearing.
Combining integer witnesses with failure certificates gives membership in $\Sigma_2^p$. The deterministic running time accounts for both chamber enumeration in fixed dimension and complementary-slackness branching.
Finally, the three-regime argument for one-ABO, cycle-only instances is valid for arbitrary horizons. Together with the reduction, it establishes the claimed restricted $\mathrm{coNP}$-completeness.
The established results need no substantive mathematical repair. The remaining blocker is the explicitly unresolved general many-one complexity classification.
⟨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.