Answer: Polynomial-time solvable in \(O((m+\tau)L^2+m^3L)\) bit operations.
Theorem 15 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a network flow game G = (N, K), where N = (V, E, s, t, c) is a series-parallel network, and an agent e ∈E, it is NP-hard to decide whether e is not a dummy player.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a two-terminal series-parallel network template, rational masses \(\mu_t\) of capacity-agent types \(t\), per-agent capacities \(a_t\), a location \(\ell(t)\) for each type, a rational target flow \(K\), and a queried type \(q\), let \(F(y)\) be the maximum flow when location \(\ell\) has capacity \(\sum_{t:\ell(t)=\ell} a_t y_t\). Decide whether there exist coalition masses \(0\le y_t\le\mu_t\) and \(0<\delta\le y_q\) such that \(F(y)\ge K>F(y-\delta e_q)\).
Let \(G=(V,E,s,r)\) be a directed two-terminal series-parallel network template with distinct terminals and \(m=|E|\ge1\); parallel edges are allowed.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types. Require \(\sum_t\mu_t=1\).
Each type \(t\) has a positive integer per-agent capacity \(a_t\), encoded in binary, and controls a single edge \(\ell(t)\in E\). Several types may control the same edge. The input also gives a binary rational threshold \(K>0\) and a queried support type \(q\).
For real coalition masses \(0\le y_t\le\mu_t\), edge \(e\) has capacity \(c_e(y)=\sum_{t:\ell(t)=e}a_ty_t\), with an empty sum equal to zero. There are no additional capacities. Let \(F(y)\) be the standard maximum nonnegative \(s\)-\(r\) flow under these capacities.
The decision problem asks whether there exist such \(y\) and a real \(\delta\) with \(0<\delta\le y_q\) such that \(F(y)\ge K>F(y-\delta e_q)\), where \(e_q\) is the unit vector in coordinate \(q\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this continuous pivotality decision problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For discrete coalitions with one agent per edge and binary-encoded positive integer capacities and threshold, deciding whether a queried agent is pivotal for some coalition is NP-hard; Shapley values admit a pseudopolynomial algorithm on series-parallel networks. [Elkind et al.](https://www.cs.ox.ac.uk/people/leslieann.goldberg/papers/mcn.pdf)
No result settling this exact continuous pivotality problem was located in the literature search.
The problem is polynomial-time solvable.
More precisely, define the full-society capacities by \(U_e=\sum_{t:\ell(t)=e}a_t\mu_t\), let \(G^+\) contain exactly the edges with \(U_e>0\), and put \(e^\star=\ell(q)\). Then the answer is yes exactly when:
An implementation without a supplied series-parallel decomposition takes \(O((m+\tau)L^2+m^3L)\) bit operations. The proof below handles equality \(K=F(\mu)\), uncontrolled edges, and several types controlling the same edge.
Fix a binary series-parallel construction tree, whose existence is part of the hypothesis. Its leaves are the distinct edges, including parallel edges.
For a subnetwork \(H\), let \(F_H(y)\) denote its maximum flow between its own terminals, using the types controlling its edges. Write \(M_H=F_H(\mu)\).
If \(H\) is the series composition of \(H_1,H_2\), then
\(F_H(y)=\min\{F_{H_1}(y),F_{H_2}(y)\}.\)
Indeed, every terminal flow restricts to flows of the same value in both children. Conversely, for any value at most both child maxima, scaling maximum flows gives child flows of that value, which concatenate.
If \(H\) is their parallel composition, then
\(F_H(y)=F_{H_1}(y)+F_{H_2}(y).\)
Every flow splits between the edge-disjoint children, and maximum child flows can be combined. Consequently,
\(M_H=\min\{M_{H_1},M_{H_2}\}\) in series, and \(M_H=M_{H_1}+M_{H_2}\) in parallel.
We will also need the following consequence of continuous coalition masses:
Every value in \([0,M_H]\) is attainable as \(F_H(y)\).
For \(M_H>0\) and a desired value \(w\), set \(y_t=(w/M_H)\mu_t\) for all types in \(H\). All capacities scale by \(w/M_H\), and maximum flow scales by the same factor: scaling feasible flows proves both inequalities. When \(M_H=0\), zero is the only attainable value.
Types in different children are disjoint because each type controls one edge. Thus child assignments can be chosen independently.
For each subnetwork \(H\) containing \(e^\star\), define \(\mathcal P_H\) to be the set of thresholds \(k>0\) for which \(q\) is pivotal in \(H\).
We may always take the removed mass to be the entire coalition mass of \(q\). Indeed, if
\(F_H(y)\ge k>F_H(y-\delta e_q)\), with \(0<\delta\le y_q\),
then capacity monotonicity gives
\(F_H(y-y_qe_q)\le F_H(y-\delta e_q)<k.\)
The converse holds by choosing \(\delta=y_q\). Hence it suffices to study full removal.
We prove that \(\mathcal P_H\) is either empty or an interval \((0,R_H]\), with an exact recurrence for \(R_H\). We use \(R_H=0\) to denote the empty case.
Suppose \(H\) consists of \(e^\star\). Put
\(A=\sum_{t\ne q:\ell(t)=e^\star}a_t\mu_t,\qquad B=a_q\mu_q>0.\)
The total capacity cannot exceed \(A+B\), so no threshold above \(A+B\) is pivotal.
Conversely, take \(0<k\le A+B\), and set
\(z=\min\{B,k\},\qquad x=k-z.\)
Then \(0<z\le B\), \(0\le x\le A\), and \(x<k\). Choose \(y_q=z/a_q\). If \(A>0\), choose \(y_t=(x/A)\mu_t\) for the other types on this edge; if \(A=0\), then \(x=0\), and choose their masses to be zero.
The edge capacity before removal is \(x+z=k\), and after removal it is \(x<k\). Therefore
\(\mathcal P_H=(0,A+B]=(0,M_H],\qquad R_H=M_H.\)
Let \(C\) be the child containing \(e^\star\), and \(S\) the other child. For a fixed assignment, write
\(v=F_C(y),\qquad u=F_C(y-y_qe_q),\qquad w=F_S(y).\)
The pivotality inequalities in the parent are
\(\min\{v,w\}\ge k>\min\{u,w\}.\)
They hold exactly when \(v\ge k>u\) and \(w\ge k\): the first parent inequality forces \(v,w\ge k\), after which the strict second inequality forces \(u<k\).
Since \(S\) can attain every value in \([0,M_S]\), independently of \(C\),
\(\mathcal P_H=\mathcal P_C\cap(0,M_S].\)
Thus
\(R_H=\min\{R_C,M_S\}.\)
This formula includes the empty cases \(R_C=0\) and \(M_S=0\).
Using the same notation, the parent inequalities are
\(v+w\ge k>u+w.\)
Equivalently, \(v\ge k-w>u\). Since \(u\ge0\), the shifted threshold \(k-w\) is positive. Independence and attainability in the sibling therefore give
\(\mathcal P_H=\{h+w:h\in\mathcal P_C,\ 0\le w\le M_S\}.\)
If \(R_C=0\), this set is empty. If \(R_C>0\), it is exactly \((0,R_C+M_S]\). To verify the nontrivial inclusion, for any \(0<k\le R_C+M_S\), choose
\(h=\min\{k,R_C\},\qquad w=k-h.\)
Then \(0<h\le R_C\) and \(0\le w\le M_S\). Consequently,
\(R_H=0\) if \(R_C=0\), and \(R_H=R_C+M_S\) otherwise.
This completes the interval induction, including its upper endpoints.
First, \(M_H>0\) exactly when \(H\) has a terminal-to-terminal path consisting entirely of edges with positive full capacities.
This follows inductively. At a leaf it is immediate. In series, positivity requires positivity in both children, and their paths concatenate. In parallel, positivity requires positivity in at least one child.
Now let \(A_H\) denote the assertion that \(e^\star\) lies on such a path between the terminals of \(H\). We claim
\(R_H=M_H\) when \(A_H\) holds, and \(R_H=0\) otherwise.
At the queried leaf, \(B>0\), so the claim follows from the leaf calculation.
For a series parent, \(A_H\) holds exactly when \(A_C\) holds and \(M_S>0\). If either condition fails, the recurrence gives \(R_H=0\). If both hold, induction gives \(R_C=M_C>0\), and hence
\(R_H=\min\{M_C,M_S\}=M_H.\)
For a parallel parent, a directed terminal path containing \(e^\star\) lies in \(C\); therefore \(A_H\) holds exactly when \(A_C\) holds. If it fails, \(R_H=0\). If it holds, induction gives \(R_C=M_C>0\), and hence
\(R_H=M_C+M_S=M_H.\)
Applying this statement at the root proves the announced criterion:
\(q\text{ is pivotal at }K\quad\Longleftrightarrow\quad K\le F(\mu)\text{ and }e^\star\text{ lies on an }s\text{-}r\text{ path in }G^+.\)
In particular, the strict inequality after removal remains achievable when \(K=F(\mu)\).
The proof uses a decomposition tree, but the algorithm does not need to construct one.
Write \(e^\star=(u,v)\).
A directed two-terminal series-parallel network is acyclic: inductively, its source has no incoming edges, its sink has no outgoing edges, and neither composition introduces a cycle. Thus the two reachability paths concatenate with \(e^\star\) into a path without repeated vertices. Also \(U_{e^\star}\ge a_q\mu_q>0\). This verifies that the reachability tests implement the required path condition.
For exact arithmetic, write each mass as \(\mu_t=p_t/d_t\), and \(K=p_K/d_K\). Use the common denominator
\(D=d_K\prod_t d_t.\)
The scaled capacities and threshold are nonnegative integers:
\(\widehat U_e=\sum_{t:\ell(t)=e}a_tp_t(D/d_t),\qquad \widehat K=p_K(D/d_K).\)
The bit length of \(D\) is \(O(L)\). All scaled capacities, their total, and the scaled threshold also have \(O(L)\) bits. Using ordinary binary multiplication and division, preprocessing takes \(O((m+\tau)L^2)\) bit operations.
Use the [Edmonds–Karp shortest augmenting path algorithm](https://deltadbu.github.io/UCAS_algorithm_course/Lectures/EdmondsKarp1972.pdf), with its standard bound of \(O(|V|m^2)\) arithmetic and graph operations. Its hypotheses hold here: the graph is finite and capacities are nonnegative integers; parallel edges can be retained as separate residual-edge pairs. All numerical operations involve \(O(L)\)-bit integers.
A two-terminal series-parallel network has \(|V|\le m+1\), as follows immediately by induction over its construction. Therefore maximum flow takes \(O(m^3L)\) bit operations. Reachability takes \(O(m)\) graph operations and is covered by the stated bound.
The total running time is consequently
\(O((m+\tau)L^2+m^3L).\)
The discrete hardness and pseudopolynomial power-index algorithm are established in [Elkind et al., Theorems 4.5 and 4.8](https://www.cs.ox.ac.uk/people/leslieann.goldberg/papers/mcn.pdf). The decisive additional property here is that each sibling subnetwork can attain every flow value in its interval \([0,M_H]\). That property makes the pivotal-threshold recursion an exact interval computation and settles this continuous problem.
⟨structured verdict parsed — rendered above⟩
The prover’s output correctly resolves the continuous problem in polynomial time. The characterization, interval recursion, and stated running time are valid under the directed two-terminal series-parallel hypothesis. I found no major or minor mathematical issues requiring repair.
The full capacities \(U_e\) correctly aggregate all support types controlling each edge. Since \(q\) is a support type and \(a_q>0\), the quantity \(B=a_q\mu_q\) is strictly positive.
The proof uses the actual support size \(\tau\), permits multiple types on one edge, and assigns capacity zero to uncontrolled edges. It introduces no additional capacities or restrictions on coalition masses.
Choosing child assignments independently is legitimate: each type controls exactly one edge, and the children have disjoint edge sets. The input normalization \(\sum_t\mu_t=1\) does not impose an additional equality constraint on the coalition vector \(y\).
Both formulas are correct for the construction used in the proof.
In series composition, the children meet only at the identified terminal. Flow conservation gives the same flow value in both children. The stated scaling and concatenation argument establishes attainability of their minimum.
In parallel composition, the children share only their terminals. Restricting a flow to the children and combining child flows establishes additivity.
These arguments apply to zero capacities and to parallel edges. The corresponding recurrences for \(M_H\) follow directly.
The uniform scaling construction is valid. When \(M_H>0\), the factor \(w/M_H\) lies in \([0,1]\), so every assigned mass respects its support bound. Capacities and maximum flow scale together.
When \(M_H=0\), all allowed assignments have maximum flow zero by capacity monotonicity. Thus the stated attainable interval remains correct, including both endpoints.
The monotonicity inequality is in the correct direction: removing all of \(y_q\) cannot produce a larger flow than removing only \(\delta\).
Consequently, an original witness remains a witness after full removal. Conversely, a full-removal witness satisfies the original definition by taking \(\delta=y_q\). The strict flow inequality ensures that such a witness cannot have \(y_q=0\), so the required positivity of \(\delta\) is preserved.
The upper bound \(A+B\) is valid.
For the proposed witness, \(z=\min\{B,k\}\) is strictly positive and at most \(B\). The quantity \(x=k-z\) is nonnegative and at most \(A\): when \(k\le B\), it is zero; otherwise the bound follows from \(k\le A+B\).
Both mass assignments therefore respect their bounds. The before-removal capacity is exactly \(k\), and the after-removal capacity is \(x<k\). The case \(A=0\) is explicitly covered.
Hence the claimed interval \(\mathcal P_H=(0,M_H]\), including its upper endpoint, is established.
The equivalence between the parent inequalities and \(v\ge k>u\), together with \(w\ge k\), is exact. In particular, once the first parent inequality forces \(w\ge k\), the second can hold only through \(u<k\).
Independence of the sibling assignment and its attainable range justify
\(\mathcal P_H=\mathcal P_C\cap(0,M_S]\).
The resulting recurrence \(R_H=\min\{R_C,M_S\}\) correctly handles an empty child pivotal set and a zero-flow sibling.
Subtracting the unchanged sibling flow gives the exact shifted threshold \(h=k-w\). Its positivity follows from \(h>u\ge0\); no nonpositive threshold is inadvertently admitted.
The stated set identity follows from child independence and sibling attainability. If the child pivotal set is empty, the parent set is empty.
Otherwise, the proposed choice \(h=\min\{k,R_C\}\), \(w=k-h\) satisfies all required bounds for every \(0<k\le R_C+M_S\). Thus the interval is exactly \((0,R_C+M_S]\), with its upper endpoint included.
The positivity characterization for \(M_H\) matches the series and parallel flow recurrences.
The path assertions also match the construction: in series, a path containing the queried edge requires the corresponding child path and a positive-capacity terminal path through the sibling; in parallel, a terminal path containing that edge lies in its child.
The induction therefore correctly establishes \(R_H=M_H\) when the queried edge lies on a positive-capacity terminal path, and \(R_H=0\) otherwise.
At the root this proves both directions of the announced criterion. It also proves pivotality at \(K=F(\mu)\), rather than merely for thresholds strictly below the full-society flow.
Directed two-terminal series-parallel networks are acyclic under the stated construction. The prover’s structural justification is valid.
Therefore the two reachability tests concatenate with \(e^\star\) into a directed path without repeated vertices. The queried edge itself has positive full capacity. Conversely, a path containing that edge supplies both reachability conditions.
The algorithm consequently implements the proved criterion without requiring a decomposition tree as input.
The common denominator \(D=d_K\prod_t d_t\) is valid without any coprimality assumption. Every division \(D/d_t\) and \(D/d_K\) is exact.
Its bit length is \(O(L)\), as are the scaled capacities, their sum, and the scaled threshold. The preprocessing bound \(O((m+\tau)L^2)\) safely covers ordinary binary multiplication, division, and aggregation.
The invoked Edmonds–Karp bound is the standard \(O(|V|m^2)\) bound for shortest augmenting paths. The graph is finite, scaled capacities are nonnegative integers, and retaining parallel edges as separate residual pairs is valid. The shortest augmenting path algorithm and its cubic bound for sparse networks are also documented in the [Princeton Algorithms materials](https://algs4.cs.princeton.edu/lectures/keynote/64MaxFlow-2x2.pdf).
The construction gives \(|V|\le m+1\). Residual-capacity updates, comparisons, and flow-value arithmetic involve \(O(L)\)-bit integers. Thus \(O(m^3L)\) bit operations for maximum flow is justified, and reachability is covered by the total bound.
The final running time \(O((m+\tau)L^2+m^3L)\) is polynomial in the requested parameters.
The cited theorem numbers are accurate: Theorem 4.5 states a pseudopolynomial Shapley-value algorithm, and Theorem 4.8 establishes NP-hardness of deciding whether a discrete edge player is not a dummy. In the monotone threshold game, the latter is precisely existence of a pivotal coalition. See [Elkind et al.](https://www.cs.ox.ac.uk/people/leslieann.goldberg/papers/mcn.pdf).
These results provide context; the continuous classification follows from the prover’s own complete argument.
Repair feedback: None required. The output establishes the claimed polynomial-time decision procedure.
⟨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.