Answer: —
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe Vickrey-nearest core payments can be computed in polynomial time by solving linear program LP-2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a directed network \(G=(V,A)\), source \(s\), sink \(g\), rational demand \(q>0\), and a distribution of provider mass \(\mu_t\) over types \(t\) that specify an arc role and unit cost \(c_t\), let \(C(z)\) be the minimum cost of a \(q\)-flow under capacities \(z\leq\mu\), and let \(x^\star\) be a tie-broken minimum-cost flow at \(\mu\). Determine the complexity, in \(|V|\), support size \(\tau\), and input bit length \(L\), of finding rates \(p_t\geq c_t\) for selected types that maximize \(P=\sum_t x^\star_t p_t\), then minimize \(\max_{t:x^\star_t>0}|p_t-v_t|\), subject to the core inequalities \(P\leq C(z)+\sum_t\min\{z_t,x^\star_t\}(p_t-c_t)\) for every \(z\leq\mu\), where \(v_t=c_t+\lim_{\varepsilon\downarrow0}[C(\mu-\varepsilon e_t)-C(\mu)]/\varepsilon\) when the limit is defined.
Given a directed network \(G=(V,A)\), let \(m=|A|\), choose distinct vertices \(s,g\), and let \(q>0\) be rational. A society is given by its support: an ordered list of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Each type specifies an arc \(a_t\in A\) and a binary-rational unit cost \(c_t\geq0\). Types on the same arc supply separate parallel capacities; arcs without providers have zero capacity.
For real capacity vectors \(0\leq z\leq\mu\), define \(C(z)=\min\{\sum_t c_ty_t:y\text{ is a nonnegative }s\text{-}g\text{ flow of value }q,\ 0\leq y\leq z\}\), with \(C(z)=+\infty\) if infeasible.
Assume \(C(\mu)<\infty\). Let \(x^\star\) be the lexicographically least minimum-cost flow under the input ordering, and put \(S=\{t:x_t^\star>0\}\).
For every \(t\in S\), require the reference rate \(v_t=c_t+\lim_{\varepsilon\downarrow0}[C(\mu-\varepsilon e_t)-C(\mu)]/\varepsilon\) to exist and be finite.
Choose real rates \(p_t\geq c_t\) for \(t\in S\); unselected types receive zero payment. Require \(P=\sum_{t\in S}x_t^\star p_t\leq C(z)+\sum_{t\in S}\min\{z_t,x_t^\star\}(p_t-c_t)\) for every real \(0\leq z\leq\mu\).
First maximize \(P\), then among its maximizers minimize \(\max_{t\in S}|p_t-v_t|\).
Is exact computation of these optimal rates polynomial-time in \(|V|,m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite edge-provider path auctions, maximizing total core payment and then minimizing \(L_\infty\) distance to VCG payments is polynomial-time computable. [Zhang et al.](https://doi.org/10.3233/978-1-61499-672-9-1485)
Related continuous-goods reverse auctions use finitely many bidders and whole-bidder coalitions. [Karaca et al.](https://arxiv.org/html/1711.06774v5) No complexity classification for the exact mass-coalition formulation above was located.
The general bounded optimization problem remains unresolved here. I prove two further results:
The verification result does not establish hardness of the particular optimization objective in the question. That distinction is the remaining gap.
The stated assumptions permit unbounded total payment.
Consider two providers on the same arc from $s$ to $g$, with
$$
\mu_1=\mu_2=\frac12,\qquad c_1=0,\qquad c_2=1,\qquad q=\frac34.
$$
The unique minimum-cost flow is
$$
x^\star=\left(\frac12,\frac14\right),\qquad C(\mu)=\frac14.
$$
For sufficiently small $\varepsilon>0$,
$$
C(\mu-\varepsilon e_1)=\frac14+\varepsilon,
\qquad
C(\mu-\varepsilon e_2)=\frac14.
$$
Thus both reference rates exist and equal $1$.
A capacity vector $z$ is feasible exactly when $z_1+z_2\geq 3/4$. For such a vector,
$$
C(z)=\frac34-z_1,
\qquad z_2\geq\frac14.
$$
Writing $d_t=p_t-c_t$, direct substitution shows that the coalition inequality's right-hand side minus its left-hand side is
$$
\left(\frac12-z_1\right)(1-d_1).
$$
Consequently, $p_1=1$ and every $p_2\geq1$ satisfy all coalition inequalities. Their total payment is
$$
P=\frac12+\frac14p_2,
$$
which is unbounded.
For the substantive complexity question below, I therefore consider instances whose maximum payment is finite.
This section proves the reductions used subsequently.
Let $B$ be the provider incidence matrix: the column of a provider on an arc from $u$ to $v$ has $+1$ at $u$ and $-1$ at $v$. Let $b_s=q$, $b_g=-q$, and all other coordinates of $b$ be zero. Define
$$
\mathcal F=\{y:By=b,\ 0\leq y\leq\mu\}.
$$
Write
$$
x=x^\star,\qquad C^\star=c^\top x,
$$
and extend $d_t=p_t-c_t$ by setting $d_t=0$ outside $S$.
The coalition inequalities are equivalent to
$$
\sum_{t\in S}d_t(x_t-y_t)_+
\leq c^\top y-C^\star
\qquad\text{for every }y\in\mathcal F,
$$
where $(a)_+=\max\{a,0\}$.
For necessity, choose $z=y$. Since $C(y)\leq c^\top y$, the coalition inequality implies
$$
C^\star+\sum_{t\in S}x_td_t
\leq c^\top y+\sum_{t\in S}\min\{y_t,x_t\}d_t.
$$
Rearranging proves the displayed condition.
For sufficiency, let $z$ be feasible and choose a minimum-cost flow $y\leq z$. Such a minimizer exists because its feasible set is nonempty and compact. Applying the displayed condition gives
$$
P\leq C(z)+\sum_{t\in S}\min\{y_t,x_t\}d_t
\leq C(z)+\sum_{t\in S}\min\{z_t,x_t\}d_t.
$$
The last inequality uses $d_t\geq0$. Infeasible $z$ impose no restriction.
Define
$$
\mathcal T=
\left\{
h:
Bh=0,\quad
h_j\geq0\text{ when }x_j=0,\quad
h_j\leq0\text{ when }x_j=\mu_j
\right\}.
$$
For each fixed $h\in\mathcal T$, sufficiently small positive $\varepsilon$ satisfy $x+\varepsilon h\in\mathcal F$. Conversely, $y-x\in\mathcal T$ for every $y\in\mathcal F$.
Positive homogeneity therefore makes the coalition inequalities equivalent to
$$
\sum_{t\in S}d_t(-h_t)_+
\leq c^\top h
\qquad\text{for every }h\in\mathcal T.
$$
Optimality of $x$ also implies
$$
c^\top h\geq0\qquad(h\in\mathcal T),
$$
because a direction of negative cost would improve $x$ by a sufficiently small step.
For $t\in S$, define
$$
\kappa_t=
\min\{c^\top h:h\in\mathcal T,\ h_t=-1\},
$$
with $\kappa_t=+\infty$ if the constraint system is infeasible.
When feasible, this linear program has an attained finite minimum: its objective is bounded below by zero, and a linear objective with finite infimum on a nonempty polyhedron attains that infimum.
Every valid rate vector satisfies
$$
0\leq d_t\leq\kappa_t
$$
when $\kappa_t$ is finite. Indeed, evaluating the directional inequality at a minimizing direction gives a left-hand side at least $d_t$.
If $\kappa_t=+\infty$, no direction in $\mathcal T$ has $h_t<0$, since such a direction could be scaled to have $h_t=-1$. Hence arbitrary nonnegative increments in coordinate $t$, with all other increments zero, satisfy every directional inequality. Since $x_t>0$, total payment is then unbounded.
It follows that
$$
\text{maximum payment is finite}
\quad\Longleftrightarrow\quad
\kappa_t<+\infty\text{ for every }t\in S.
$$
These quantities are computable by polynomially many rational linear programs of polynomial size.
When all $\kappa_t$ are finite, the valid increment set is closed, nonempty, and contained in the compact box
$$
\prod_{t\in S}[0,\kappa_t].
$$
It is nonempty because $d=0$ is valid. Both optimization stages consequently attain their optima.
If $0<x_t<\mu_t$, reducing $\mu_t$ slightly leaves $x$ feasible. The optimum cost therefore remains $C^\star$, giving
$$
v_t=c_t.
$$
Suppose instead that $x_t=\mu_t$ and $\kappa_t$ is finite. Any flow $y$ feasible under capacity $\mu-\varepsilon e_t$ gives
$$
h=\frac{y-x}{\varepsilon}\in\mathcal T,\qquad h_t\leq-1.
$$
Set $a=-h_t\geq1$. Then $h/a$ is feasible in the definition of $\kappa_t$, so
$$
c^\top h\geq a\kappa_t\geq\kappa_t.
$$
Thus
$$
C(\mu-\varepsilon e_t)\geq C^\star+\varepsilon\kappa_t.
$$
Conversely, a minimizing direction with $h_t=-1$ makes $x+\varepsilon h$ feasible under the reduced capacity for every sufficiently small positive $\varepsilon$. This gives the reverse inequality. Hence, for sufficiently small $\varepsilon$,
$$
C(\mu-\varepsilon e_t)=C^\star+\varepsilon\kappa_t,
$$
and
$$
v_t=c_t+\kappa_t.
$$
In particular, bounded instances satisfy all reference-rate promises, and their reference rates are exactly computable in polynomial time.
Construct the residual graph at $x$. Provider $j$ contributes:
Keep provider identities even when several residual arcs have the same endpoints.
Call a directed simple residual cycle admissible if it does not consist of the forward and reverse copies of the same provider. Here a simple cycle has no repeated vertex except its initial and final vertex.
A nonnegative increment vector $d$ satisfies all coalition inequalities if and only if every admissible directed simple residual cycle has nonnegative weight.
Given $h\in\mathcal T$, place residual flow $h_j$ on the forward copy when $h_j>0$, and $-h_j$ on the reverse copy when $h_j<0$. The sign restrictions defining $\mathcal T$ ensure that these residual arcs exist. The equation $Bh=0$ makes this residual flow a circulation.
Its weight is
$$
c^\top h-\sum_{t\in S}d_t(-h_t)_+.
$$
For each provider, its support uses at most one residual direction. A nonnegative circulation decomposes into nonnegative multiples of directed simple cycles, using only arcs in its support. Every cycle in this decomposition is therefore admissible.
If every admissible cycle has nonnegative weight, the circulation has nonnegative weight. This proves all directional inequalities.
Conversely, an admissible simple cycle uses each provider in at most one direction. Its signed provider vector $h$ belongs to $\mathcal T$, and the cycle's weight equals
$$
c^\top h-\sum_{t\in S}d_t(-h_t)_+.
$$
A negative admissible cycle therefore violates a directional inequality. ∎
This characterization gives a finite rational linear description of valid increments. Each cycle inequality has the form
$$
\sum_{\substack{t\in S\\
\text{cycle uses the reverse copy of }t}}d_t
\leq
\sum_{\text{forward copies}}c_t-
\sum_{\text{reverse copies}}c_t.
$$
Each cycle has at most $|V|$ arcs, so every such inequality has polynomial encoding length.
It also explains why ordinary negative-cycle detection is insufficient. A partially used provider has both residual copies, and their combined weight is
$$
c_t+(-c_t-d_t)=-d_t.
$$
For $d_t>0$, this is a negative two-arc cycle, but it represents cancellation of the same provider coordinate and imposes no coalition constraint.
Define RATE-VALIDITY as follows: given an instance satisfying the task's promises and a rational rate vector $p_t\geq c_t$, decide whether all coalition inequalities hold.
I prove hardness even when maximum payment is finite. The candidate rates' encoding length is included in the verification input length.
The lexicographically least minimum-cost flow can be computed by first minimizing cost and then successively minimizing each coordinate while fixing the previously obtained optimum values. These are polynomially many rational linear programs.
By Section 3, an invalid rate vector has an admissible negative simple cycle as a certificate. Its length is at most $|V|$. Its residual availability, admissibility, and negative rational weight can all be checked in polynomial time.
Thus RATE-VALIDITY belongs to $\mathrm{coNP}$ on the promised inputs.
I use the known $\mathrm{NP}$-completeness of detecting a negative simple cycle in a rationally weighted mixed graph. A mixed graph has directed arcs and undirected edges; a cycle respects directed arcs and does not traverse the same undirected edge out and back as a two-step cycle. This is the result of [Arkin and Papadimitriou, *On negative cycles in mixed graphs*](https://doi.org/10.1016/0167-6377(85)90013-6). The corresponding exclusion of artificial opposite-arc cycles is also stated explicitly in [Király, *Shortest Paths in Nearly Conservative Digraphs*](https://arxiv.org/pdf/1409.7033).
Multiplying lengths by the product of their denominators makes them integral in polynomial bit length and preserves all cycle signs. Thus assume integral lengths below.
Replace each nonnegative undirected edge by its two directed copies, with the same length. This preserves existence of a negative simple cycle: the only newly represented use of both copies of one edge is a two-arc cycle of nonnegative weight.
The remaining undirected edges have lengths $-r_e$, where $r_e$ is a positive integer.
If these negative edges contain an undirected cycle, that cycle is already negative. This case can be answered directly. Otherwise they form a forest $F$.
For each edge $e=\{u_e,v_e\}$ of $F$, choose an ordering of its endpoints. Construct a directed baseline graph by replacing it with
$$
u_e\longrightarrow v_e\text{ of length }r_e,
\qquad
v_e\longrightarrow u_e\text{ of length }-r_e.
$$
Keep all ordinary directed arcs unchanged.
If the baseline graph has a negative cycle, the source mixed graph has a negative cycle too. Indeed, returning the raised length $r_e$ to $-r_e$ can only decrease cycle length. A negative simple baseline cycle cannot be the two copies of one forest edge, whose total baseline length is zero.
Assume henceforth that the baseline graph has no negative cycle. Add a temporary source with zero-length arcs to every vertex and let $\pi(u)$ be shortest-path distances. Reweight every arc $uv$ of length $w$ to
$$
w+\pi(u)-\pi(v).
$$
All reweighted baseline lengths are nonnegative, and reweighting preserves cycle lengths.
For a forest edge, shortest-path inequalities in both directions give
$$
\pi(v_e)=\pi(u_e)+r_e.
$$
Its two baseline copies therefore both have reweighted length zero. Its source-graph copies instead have reweighted lengths
$$
u_e\longrightarrow v_e:\ -2r_e,
\qquad
v_e\longrightarrow u_e:\ 0.
$$
Let $N$ be the number of source vertices. Choose a positive dyadic rational $\delta$ with $N\delta<1$ and add $\delta$ to every ordinary directed arc. Their lengths are now strictly positive.
This perturbation preserves existence of a negative simple cycle. A source cycle has integral total length before perturbation and uses at most $N$ arcs. Thus a negative cycle remains negative, because its perturbed length is at most $-1+N\delta<0$; a nonnegative cycle cannot become negative.
Call the resulting graph the core graph. Its special pairs have lengths $0$ and $-2r_e$, and all ordinary arcs have positive lengths.
Let $k=|E(F)|$. The case $k=0$ is an ordinary directed negative-cycle problem and can be handled directly. Assume $k>0$.
Introduce new vertices $s,g$. For each forest edge $e$, introduce three selected providers:
| Provider | Original arc | Unit cost | Intended flow | Capacity |
|---|---|---:|---:|---:|
| $t_e$ | $v_e\to u_e$ | $0$ | $\alpha$ | $2\alpha$ |
| $L_e$ | $s\to v_e$ | $0$ | $\alpha$ | $\alpha$ |
| $R_e$ | $u_e\to g$ | $0$ | $\alpha$ | $\alpha$ |
For each ordinary core arc, introduce an unused provider of its strictly positive core length as unit cost and capacity $\alpha$.
Set
$$
D=\sum_e2r_e,\qquad H=D+1.
$$
Add these unused replacement providers, each with capacity $\alpha$:
If there are $\ell$ ordinary core arcs, the capacities listed so far sum to
$$
(7k+\ell)\alpha.
$$
Choose $\alpha$ to be a positive dyadic rational with this sum less than $1$. Add one zero-cost provider on an isolated arc between two further new vertices, with mass
$$
1-(7k+\ell)\alpha.
$$
All masses are positive dyadic rationals and sum to one.
Set
$$
q=k\alpha.
$$
The intended flow sends $\alpha$ along each path
$$
s\longrightarrow v_e\longrightarrow u_e\longrightarrow g.
$$
The intended flow is feasible and costs zero. Every ordinary or replacement provider has strictly positive cost. Therefore, any minimum-cost flow uses only the zero-cost selected providers and the isolated provider.
The isolated provider carries zero flow by conservation at its endpoints.
The only remaining arcs leaving $s$ are the $L_e$ providers. Their total capacity is exactly $q$, so each must carry its full capacity $\alpha$. The same argument at $g$ forces every $R_e$ to carry $\alpha$.
These boundary flows fix the divergence required of the forest providers $t_e$. Their incidence columns are linearly independent: on an undirected forest, leaf elimination shows that an incidence-kernel vector must be zero. Hence their flows are uniquely determined and equal $\alpha$.
Thus the intended flow is the unique minimum-cost flow and therefore equals $x^\star$, independently of provider ordering.
For each selected provider, its corresponding replacement provider permits a direction decreasing the selected coordinate by one and increasing the replacement coordinate by one. Both providers are on the same original arc, so this direction preserves conservation.
Its cost is $2r_e$ for $t_e$ and $H$ for $L_e,R_e$. Section 2 therefore gives
$$
d_{t_e}\leq2r_e,\qquad
d_{L_e}\leq H,\qquad
d_{R_e}\leq H.
$$
Maximum payment is finite.
Each $t_e$ is partially used, so its reference rate is zero. Each $L_e,R_e$ is saturated and has finite $\kappa_t$ by its replacement direction. Section 2.4 proves that its reference derivative exists and is finite. All task promises hold.
Supply the candidate rates
$$
p_{t_e}=2r_e,\qquad p_{L_e}=p_{R_e}=0.
$$
All selected original costs are zero, so these are also the increments.
On the core vertices, the residual copies of $t_e$ have weights
$$
v_e\longrightarrow u_e:\ 0,
\qquad
u_e\longrightarrow v_e:\ -2r_e.
$$
Together with the ordinary providers, these reproduce the core graph.
The partial-provider replacement on $v_e\to u_e$ has residual weight $2r_e$. It creates no additional negative admissible cycle:
Any residual simple cycle visiting $s$ or $g$ must use a star replacement arc of weight $H$. The only negative residual arcs anywhere are the reverse copies of the $t_e$, whose total possible negative contribution to a simple cycle is at least $-D$. Such a cycle therefore has weight at least
$$
H-D=1>0.
$$
The isolated provider lies on no cycle.
Consequently,
$$
\text{candidate rates are valid}
\quad\Longleftrightarrow\quad
\text{the source mixed graph has no negative simple cycle}.
$$
All quantities and the number of providers have polynomial encoding length. The directly decidable preprocessing cases can be mapped to fixed bounded promised instances: two parallel providers with masses $1/2$, costs $0,1$, and demand $1/4$ have valid selected rate $0$ and invalid selected rate $2$.
This completes the many-one reduction from mixed-graph conservativity, proving the asserted $\mathrm{coNP}$-completeness.
Let
$$
I=\{t:0<x_t<\mu_t\}.
$$
I first justify its forest structure, then give a polynomial-time separation algorithm when it has at most one nontrivial connected component.
The lexicographically least minimum-cost flow is a vertex of $\mathcal F$.
Indeed, suppose
$$
x=\theta y+(1-\theta)z,\qquad 0<\theta<1,
$$
for distinct $y,z\in\mathcal F$. Since both costs are at least $C^\star$ and their weighted average equals $C^\star$, both are minimum-cost flows. At their first differing coordinate, one is strictly smaller than their convex combination, while all earlier coordinates agree. That flow is lexicographically smaller than $x$, a contradiction.
If the incidence columns indexed by $I$ were dependent, a nonzero kernel vector supported on $I$ would permit sufficiently small perturbations of $x$ in both directions, contradicting extremality.
An undirected cycle among the providers in $I$ gives such a signed incidence-kernel vector. Hence their underlying undirected graph is a forest.
Assume $I$ is nonempty and forms one undirected tree $T$, with vertex set $W$. Its residual arcs have weights
$$
u\longrightarrow v:\ c_t,
\qquad
v\longrightarrow u:\ -c_t-d_t
$$
for a provider $t$ on $u\to v$.
Delete all these tree residual arcs. For each tree provider, add two auxiliary arcs:
$$
u\longrightarrow v:\ c_t+d_t,
\qquad
v\longrightarrow u:\ -c_t.
$$
Keep every residual arc outside $T$. Call the resulting graph $R_o$.
An auxiliary arc's weight is the negative of the weight of the opposite actual tree arc. It is also at least the weight of the actual tree arc in the same direction.
For $u,v\in W$, let $t(v,u)$ be the weight of the unique actual residual tree path from $v$ to $u$.
The candidate increment vector is valid if and only if both conditions hold:
$$ \operatorname{dist}_{R_o}(u,v)+t(v,u)\geq0 \qquad(u,v\in W). $$
An unreachable distance is interpreted as $+\infty$.
Suppose $R_o$ has a negative simple cycle. Replace each auxiliary arc by the actual tree arc in the same direction. This can only decrease its weight.
The resulting cycle is admissible. The only possible exception would be a two-arc cycle consisting of one provider's opposite auxiliary copies, but its auxiliary weight is $d_t\geq0$, so it could not have been negative.
Now suppose $R_o$ has no negative cycle but the distance condition fails for $u,v$. Choose a shortest simple ordinary path $P$ from $u$ to $v$ and append the actual tree path $Q$ from $v$ to $u$. Their closed walk has negative weight.
Decompose this walk into simple cycles. The actual tree path uses each provider at most once and never in both directions. Thus a two-arc component using opposite copies of one tree provider has at least one auxiliary copy. Its weight is either zero or $d_t\geq0$:
$$
c_t+(-c_t)=0,
$$
$$
(-c_t-d_t)+(c_t+d_t)=0,
$$
or
$$
(c_t+d_t)+(-c_t)=d_t.
$$
Therefore some negative component is not such a pair. Replacing its auxiliary arcs by actual arcs gives an admissible negative residual cycle.
By Section 3, either failure yields a violated coalition inequality. This also supplies a polynomial-size separating certificate.
Assume both conditions hold. Let $C$ be an admissible simple residual cycle.
If it contains no actual tree arc, it is a cycle of $R_o$ and has nonnegative weight.
Otherwise, partition its traversal at the vertices belonging to $W$. Each segment is either an actual tree arc or an ordinary path between two tree vertices. An ordinary segment from $u$ to $v$ has weight at least
$$
\operatorname{dist}_{R_o}(u,v)\geq-t(v,u).
$$
The unique auxiliary tree path from $u$ to $v$ has weight exactly $-t(v,u)$. Replace every ordinary segment by that auxiliary path. This produces a closed walk on the tree, of weight at most the weight of $C$.
Consider one tree provider, oriented forward as $u\to v$. Write its four weights as
$$
\text{actual forward}:c,\qquad
\text{actual reverse}:-c-d,
$$
$$
\text{auxiliary forward}:c+d,\qquad
\text{auxiliary reverse}:-c.
$$
Let $F,R,L_F,L_R$ be their numbers of occurrences in the resulting walk. Since only arcs from the original admissible simple cycle are actual,
$$
F,R\in\{0,1\},\qquad F+R\leq1.
$$
A closed walk on a tree crosses each edge equally often in the two directions, so
$$
F+L_F=R+L_R.
$$
This edge's total contribution is consequently
$$
cF+(-c-d)R+(c+d)L_F-cL_R
=d(L_F-R).
$$
If $R=0$, it is nonnegative. If $R=1$, then $F=0$ and the balance equation gives $L_F=1+L_R$, so it is again nonnegative.
Every tree edge contributes nonnegative weight. The replacement walk, and therefore $C$, has nonnegative weight. Section 3 proves validity. ∎
The proposition gives a polynomial-time strong separation oracle:
All these operations use graphs of polynomial size and rational weights of polynomial encoding length. If $I$ is empty, ordinary residual negative-cycle detection already supplies the oracle.
To obtain exact optimization, use the standard rational-polyhedron theorem: a polynomial-time strong separation oracle, together with a polynomial bound on inequality encoding length, permits exact rational linear optimization in polynomial time, including for lower-dimensional polyhedra. See [Grötschel, Lovász, and Schrijver, *Rational Polyhedra*](https://doi.org/10.1007/978-3-642-78240-4_7).
Its hypotheses hold here:
First maximize
$$
P=C^\star+\sum_{t\in S}x_td_t.
$$
On bounded instances, let its exact optimum be $P^\star$. Then impose $P=P^\star$, introduce $\Delta\geq0$, and minimize $\Delta$ subject to
$$
-\Delta\leq c_t+d_t-v_t\leq\Delta
\qquad(t\in S).
$$
These additional constraints have polynomial encoding length and are directly separable. Both stages therefore run in polynomial time.
This subclass allows arbitrarily many partially used providers; it extends the previously established saturated-provider case.
As a check on the characterization, I compared the one-tree criterion with exhaustive admissible-cycle enumeration on $1000$ randomly generated small weighted instances. All agreed. This computation is supplementary; the proof above establishes the result.
The verification reduction proves that a general polynomial-time separation oracle for valid rates would imply $\mathrm P=\mathrm{NP}$. It therefore identifies a substantive obstruction to the straightforward linear-programming approach.
It does not classify the requested optimization. Optimization–separation equivalence concerns optimization for arbitrary rational objective vectors. Here the first-stage coefficients are specifically the selected flow quantities $x_t^\star$, and the second stage uses the prescribed reference rates. The reduction above does not show how an algorithm for those particular objectives would test an arbitrary candidate rate vector.
Thus the remaining task is either:
⟨structured verdict parsed — rendered above⟩
The output establishes substantial partial results, but it does not classify the requested two-stage optimization on general instances. I found no false central mathematical step. The principal remaining gap is explicitly acknowledged by the prover. There is also a minor omission in the specification of the strong separation oracle.
The target is exact computation of the rates maximizing the prescribed payment objective and then minimizing distance to the prescribed reference rates.
The output instead establishes:
These are genuine results. Neither the verification hardness result nor the tree algorithm resolves the general optimization question.
Major issue — unresolved target: The restriction to bounded instances is explicitly introduced, and the complexity classification on that restriction remains open. The unbounded example exposes an existence problem in the original formulation; it does not classify computation when optimal rates exist.
Minimum needed: Supply an argument classifying the prescribed two-stage computation on general bounded promised instances. An arbitrary-objective optimization result or a rate-validity result alone would not suffice.
All calculations check out.
The capacity and demand constraints force
$$
x^\star=\left(\frac12,\frac14\right),
\qquad C^\star=\frac14.
$$
Reducing the first capacity requires additional use of the cost-one provider; reducing the second capacity sufficiently slightly leaves the displayed optimum feasible. Thus both reference rates are indeed $1$.
For feasible $z$, its coordinate bounds imply
$$
z_1\leq\frac12,
\qquad z_2\geq\frac14,
$$
and the stated formula for $C(z)$ follows. The stated coalition slack is correct. Setting $p_1=1$ makes it zero for every feasible coalition, independently of $p_2\geq1$.
This is a valid, nondegenerate counterexample to existence of a finite maximum under the task’s promises.
Both directions of the equivalence are valid.
Necessity correctly uses $z=y$ and the inequality $C(y)\leq c^\top y$. Equality is unnecessary.
Sufficiency correctly chooses an attained minimum-cost flow under $z$, uses $y\leq z$, and relies on $d_t\geq0$ for the final monotonicity inequality. Infeasible capacity vectors impose no restriction.
The domain restrictions and the extension $d_t=0$ outside $S$ are consistent throughout.
The cone $\mathcal T$ is the correct feasible-direction cone at $x$. Every fixed direction admits a sufficiently small positive step because the remaining coordinates have positive slack in both relevant bounds.
Conversely, every difference $y-x$ obeys the cone’s sign restrictions and conservation equation.
The coalition expression is positively homogeneous in the displacement, so the directional equivalence is justified. The nonnegativity of $c^\top h$ follows from optimality of $x$ and the available small step.
The boundedness argument is correct.
A feasible defining program for $\kappa_t$ has objective bounded below by zero. The stated polyhedral attainment fact applies. Evaluating the directional inequality at its minimizer gives $d_t\leq\kappa_t$.
If that program is infeasible, positive scaling excludes every direction decreasing coordinate $t$. Consequently, increasing only $d_t$ imposes no additional directional restriction and makes payment unbounded because $x_t>0$.
The resulting compactness and attainment claims on bounded instances are valid.
The reference-rate calculation also checks out:
The asserted polynomial computation uses rational linear programs of polynomial size. No missing mathematical lemma blocks these results.
The characterization is correct.
The residual circulation constructed from a direction uses at most one residual direction of each provider. Its weight is exactly the directional slack. A circulation decomposition therefore yields only admissible cycles.
Conversely, a simple cycle other than the excluded opposite-copy pair uses each provider in at most one direction and determines a feasible direction with the stated weight.
Provider identities are essential, and the output explicitly retains them. The discussion of artificial negative opposite-copy cycles is accurate.
The finite cycle description has polynomial-length individual inequalities: each simple cycle has at most $|V|$ arcs, and summing polynomially many input rationals preserves polynomial encoding length.
The cited mixed-graph hardness premise is supported by the original authors’ publication record and by the cited Király paper. Király also distinguishes genuine cycles from artificial opposite-edge traversals. [Arkin–Papadimitriou publication record](https://researchconnect.suny.edu/en/publications/on-negative-cycles-in-mixed-graphs/), [Király’s paper](https://arxiv.org/pdf/1409.7033).
The reduction checks out step by step:
Membership in $\mathrm{coNP}$ follows from the polynomial-length admissible negative-cycle certificate. Thus the verification result is established.
The extremality argument is sound. In a nontrivial convex decomposition, both endpoints are minimum-cost flows, and their first differing coordinate contradicts lexicographic minimality.
Linear dependence among partially used incidence columns would permit perturbations in both directions. Therefore the underlying provider multigraph is a forest.
The auxiliary weights are correct. They both negate the opposite actual weight and dominate the actual weight in the same direction.
The necessity argument properly handles opposite-copy components: their possible auxiliary/actual combinations have weights $0$ or $d_t$, hence are nonnegative. A remaining negative simple component converts to an admissible residual cycle.
The sufficiency calculation is correct:
$$
cF+(-c-d)R+(c+d)L_F-cL_R=d(L_F-R).
$$
Edge-crossing balance and admissibility make this nonnegative in both cases considered. Consequently, the criterion establishes validity.
The separation-to-optimization theorem is applicable to well-described rational polyhedra, including lower-dimensional ones. The cited chapter describes that scope. The cycle description, polynomial coefficient lengths, computed bounds, and exact rational objectives supply the relevant hypotheses. [Grötschel–Lovász–Schrijver, *Rational Polyhedra*](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf).
The second-stage equality and distance constraints are correctly formulated. The resulting algorithm establishes the claimed bounded single-tree subclass.
Minor issue — oracle domain: The listed graph checks alone are not a strong separation oracle for the full feasible increment set on arbitrary rational query points. They assume $d_t\geq0$. A query with a negative increment can pass those checks while violating an explicit feasible-set constraint.
Minimum clarification: State that the oracle first checks nonnegativity and any imposed coordinate bounds, returning a violated explicit inequality before applying the graph criterion. This is a routine expositional completion.
The reported random experiment is not reproducible from the supplied output. Since it is expressly supplementary, it contributes no necessary evidence to the proof.
The concluding limitation is mathematically correct. A general polynomial-time separation oracle would decide the hard verification problem. However, optimization–separation equivalence does not automatically transform an algorithm for the particular payment objective and reference-rate tie-breaker into arbitrary-objective optimization or candidate-rate verification.
The direction is worth continuing: the output supplies a rigorous obstruction and a substantial tractable subclass. The general requested classification remains unresolved.
⟨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.