Answer: Constructive Schulze addition is $\mathrm{NP}$-complete; destructive Schulze addition is in $\mathrm{P}$; constructive and destructive ranked-pairs addition are both $\mathrm{NP}$-complete.
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateSchulze and ranked pairs resist constructive CONTROL-ADD-ALT. Ranked pairs resists destructive CONTROL-ADD-ALT.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given old alternatives \(C\), possible additions \(C'\), a rational mass distribution \(\mu\) over complete rankings of \(C\cup C'\), a favored alternative \(c\in C\), a quota \(k\), and the rule and control mode, is there a set \(S\subseteq C'\) with \(|S|\le k\) such that, after restricting each ranking to \(C\cup S\), \(c\) is the unique winner in the constructive case or is no longer the unique winner in the destructive case?
Given disjoint finite sets of old alternatives \(C\ne\varnothing\) and possible additions \(C'\), let \(m=|C\cup C'|\). The input includes \(c\in C\), an integer quota \(0\le k\le |C'|\), a rule (Schulze or ranked pairs), and a mode (constructive or destructive).
A society is given by its support: the list of the \(\tau\) strict complete rankings of \(C\cup C'\) with positive mass, each mass a binary rational, with masses summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length. State running times in \(m,\tau,L,k\).
For distinct alternatives define \(D(a,b)=\mu(a\succ b)-\mu(b\succ a)\). On any retained set \(A\), use the complete directed graph with edge weights \(D(a,b)\), including zero and negative weights.
For Schulze, let \(B_A(a,b)\) be the maximum, over simple directed paths from \(a\) to \(b\) in \(A\), of the minimum edge weight. Its winner set is \(W(A)=\{a\in A: B_A(a,b)\ge B_A(b,a)\text{ for every }b\in A\setminus\{a\}\}\).
For ranked pairs, process all ordered pairs of distinct retained alternatives in decreasing order of \(D(a,b)\), breaking ties lexicographically by fixed alternative labels. Starting with an empty directed graph, lock each edge unless it creates a directed cycle; \(W(A)\) is the singleton containing the final graph's unique source. The tie order is restricted from the full alternative set and cannot be changed by the controller.
A feasible action selects \(S\subseteq C'\) with \(|S|\le k\), restricts every ranking to \(A=C\cup S\), and preserves its mass. Success means \(W(A)=\{c\}\) constructively and \(W(A)\ne\{c\}\) destructively.
For each of the four rule–mode combinations, is deciding whether a successful action exists in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
With explicitly listed unweighted voters, constructive addition control is \(\mathrm{NP}\)-hard for both rules, and destructive addition control is \(\mathrm{NP}\)-hard for ranked pairs ([Parkes–Xia, 2012](https://cdn.aaai.org/ojs/8258/8258-13-11786-1-2-20201228.pdf)).
Destructive addition control for discrete Schulze elections is still listed as open in [Maushagen et al., 2024](https://www.ijcai.org/proceedings/2024/0326.pdf). No result for exactly the rational-mass support model above was located.
For the exact rules and success conditions in the question, the classification is:
| Rule | Constructive addition | Destructive addition |
|---|---|---|
| Schulze | $\mathrm{NP}$-complete | $\mathrm{P}$ |
| Ranked pairs | $\mathrm{NP}$-complete | $\mathrm{NP}$-complete |
The main result proved below is the polynomial-time algorithm for destructive Schulze addition. Its essential step is to replace an initially witnessing opponent by the last vertex on a witnessing path that is unreachable from $c$ above a chosen threshold.
The 2024 paper lists destructive Schulze addition as open in both winner models. The argument below supplies an algorithm for the particular unique-winner destruction objective specified here. [Maushagen et al., Section 6](https://www.ijcai.org/proceedings/2024/0326.pdf)
All arguments include zero and negative margins. If $m=1$, the sole alternative is always the unique winner, so constructive control succeeds and destructive control fails.
Put $U=C\cup C'$ and
$$
h=\left\lceil\log_2(m+1)\right\rceil.
$$
Index alternatives in their fixed label order. This preserves the prescribed lexicographic tie-breaking.
Write the $\tau$ input masses as $p_i/q_i$. Define
$$
Q=\prod_{i=1}^{\tau}q_i,
\qquad
w_i=p_i(Q/q_i).
$$
Then $w_i$ are positive integers and
$$
\sum_{i=1}^{\tau}w_i=Q.
$$
For distinct $a,b\in U$, let $\varepsilon_i(a,b)$ equal $1$ if ranking $i$ places $a$ above $b$, and $-1$ otherwise. Thus
$$
M(a,b)=\sum_{i=1}^{\tau}w_i\varepsilon_i(a,b),
\qquad
D(a,b)=\frac{M(a,b)}{Q}.
$$
The integers $Q,w_i,M(a,b)$ have $O(L)$ bits: the bit length of $Q$ is bounded by the sum of the denominator bit lengths, while $w_i\le Q$ and $|M(a,b)|\le Q$.
Restricting a ranking does not change a retained pairwise comparison. Therefore this matrix serves every feasible action.
Using schoolbook arithmetic, a conservative preprocessing bound, including sorting margin values, is
$$
T_{\mathrm{pre}}
=
O\!\left(
\tau L^2+\tau m^2L+m^2Lh
\right).
$$
Let the distinct positive margin magnitudes be
$$
0<\delta_1<\cdots<\delta_q.
$$
There are at most $\binom m2$ of them. On the occurring margin values, define
$$
f(0)=0,
\qquad
f(\delta_j)=2j,
\qquad
f(-\delta_j)=-2j.
$$
This is strictly increasing and preserves antisymmetry. Put
$$
F(a,b)=f(D(a,b)).
$$
For every simple path $P$,
$$
\min_{e\in P}F(e)
=
f\!\left(\min_{e\in P}D(e)\right).
$$
Because there are finitely many simple paths between distinct vertices,
$$
B_A^F(a,b)=f(B_A^D(a,b)).
$$
Consequently, all Schulze winner comparisons, including equalities, are preserved on every retained set.
For ranked pairs, the transformation preserves the ordering and equality classes of edge weights. Labels remain unchanged, so the full processing order is unchanged. Induction over that order shows that every locking decision is unchanged.
Thus, after preprocessing, both rules can use integer weights with $O(h)$ bits.
For Schulze, max–min Floyd–Warshall computes strongest-path values. Initialize off-diagonal entries with the edge weights, diagonal entries with a formal $+\infty$, and apply
$$
B(a,b)\leftarrow
\max\{B(a,b),\min\{B(a,z),B(z,b)\}\}.
$$
The recurrence is valid with negative weights. Concatenation produces walks, and deleting a cycle cannot decrease a walk’s minimum edge weight. Hence allowing walks gives the same maximum bottleneck as allowing simple paths between distinct endpoints.
Verification takes
$$
O(m^3h)
$$
bit operations after preprocessing.
For ranked pairs, filter the precomputed edge order to the retained alternatives and maintain the locked graph’s transitive closure. An edge $a\to b$ creates a cycle exactly when $b$ already reaches $a$. An accepted insertion updates the closure in $O(m^2)$ table operations, giving the conservative verification bound
$$
O(m^4h).
$$
The final acyclic graph has a unique source. For every pair of distinct vertices, processing an edge either establishes reachability in its direction or rejects it because reverse reachability already exists. Thus every pair is comparable by final reachability. Two distinct sources would contradict this comparability, and every nonempty finite acyclic graph has a source.
A certificate lists at most $k$ additions and uses $O(kh)$ bits. Therefore all four problems belong to $\mathrm{NP}$.
We first prove the criterion needed by the destructive algorithm.
Lemma. For every retained set $A$ containing $c$,
$$
W(A)=\{c\}
\quad\Longleftrightarrow\quad
B_A(c,d)>B_A(d,c)
\text{ for every }d\in A\setminus\{c\}.
$$
Proof. For distinct $a,b,z\in A$, concatenating strongest paths and removing cycles gives
$$
B_A(a,z)\ge
\min\{B_A(a,b),B_A(b,z)\}.
$$
Define $a\triangleright b$ when
$$
B_A(a,b)>B_A(b,a).
$$
This relation is asymmetric. We show it is transitive.
Suppose $a\triangleright b$ and $b\triangleright z$. These assumptions exclude $z=a$. Write
$$
x=B_A(a,b),
\qquad
y=B_A(b,z),
\qquad
t=B_A(z,a).
$$
If $t\ge\min\{x,y\}$, then:
$$
B_A(b,a)\ge\min\{y,t\}\ge x,
$$
contradicting $a\triangleright b$.
$$
B_A(z,b)\ge\min\{t,x\}\ge y,
$$
contradicting $b\triangleright z$.
Hence
$$
B_A(z,a)<\min\{x,y\}\le B_A(a,z),
$$
which proves transitivity.
By definition, Schulze winners are exactly the vertices having no incoming $\triangleright$ relation. In a finite transitive asymmetric relation, every dominated vertex is dominated by an undominated vertex. Indeed, repeatedly choose an incoming dominator. Repetition would, by transitivity, contradict asymmetry, so the process terminates; transitivity makes its terminal vertex dominate the initial vertex.
If $c$ is the sole undominated vertex, this observation shows that $c\triangleright d$ for every $d\ne c$. Conversely, if $c\triangleright d$ for every $d\ne c$, then $c$ is undominated and every other vertex is dominated. This proves the lemma. $\square$
Negating its conclusion gives
$$
W(A)\ne\{c\}
\quad\Longleftrightarrow\quad
\exists d\in A\setminus\{c\}:
B_A(d,c)\ge B_A(c,d).
$$
For a vertex set $X$ and a threshold $t$, define:
Reachability includes a length-zero path from a vertex to itself.
For distinct endpoints, finiteness of the simple-path set gives
$$
B_X(a,b)>t
\quad\Longleftrightarrow\quad
b\text{ is reachable from }a\text{ in }G_{>t}(X),
$$
and likewise with $\ge t$.
Let $\mathcal T$ be the set of all occurring edge weights:
$$
\mathcal T=\{D(a,b):a,b\in U,\ a\ne b\}.
$$
Its size is at most $m(m-1)$.
Fix $t\in\mathcal T$ and $d\in U\setminus\{c\}$. Define
$$
V_0=C\cup\{d\}
$$
and
$$
R_{t,d}
=
\{r\in V_0:
d\text{ is reachable from }r
\text{ in }G_{>t}(V_0)\}.
$$
In particular, $d\in R_{t,d}$.
If $c\in R_{t,d}$, discard this pair $(t,d)$.
Otherwise, define the allowable additional alternatives
$$
E_{t,d}
=
\left\{
x\in C'\setminus\{d\}:
D(x,r)\le t
\text{ for every }r\in R_{t,d}
\right\},
$$
and put
$$
V_{t,d}=V_0\cup E_{t,d}.
$$
Safe-set property. There is no path from $c$ to $d$ in $G_{>t}(V_{t,d})$.
Proof. No vertex of $V_0\setminus R_{t,d}$ has an edge of weight greater than $t$ into $R_{t,d}$. Such an edge, followed by a path to $d$, would put that vertex in $R_{t,d}$.
By definition, no vertex of $E_{t,d}$ has an edge of weight greater than $t$ into $R_{t,d}$ either.
Thus $G_{>t}(V_{t,d})$ has no edge entering $R_{t,d}$ from its complement. Since $c\notin R_{t,d}$ and $d\in R_{t,d}$, the claimed path cannot exist. $\square$
For every pair $(t,d)$ not discarded above, find a minimum-cost path from $d$ to $c$ in
$$
G_{\ge t}(V_{t,d}).
$$
Assign vertex cost $0$ to old alternatives and $1$ to possible additions. Specifically, initialize the distance at $d$ as
$$
\mathbf 1_{\{d\in C'\}},
$$
and assign an edge $a\to b$ cost
$$
\mathbf 1_{\{b\in C'\}}.
$$
A simple path’s cost is exactly its number of additional alternatives. All costs are nonnegative, so a minimum-cost walk can be made simple by deleting cycles without increasing cost. Standard shortest-path algorithms therefore compute the required minimum.
Return yes if any such minimum is at most $k$; otherwise return no.
Suppose the algorithm finds a simple path $P$ of cost at most $k$ for $(t,d)$. Select
$$
S=V(P)\cap C',
\qquad
A=C\cup S.
$$
Then $|S|\le k$, and $P$ proves
$$
B_A(d,c)\ge t.
$$
Also $A\subseteq V_{t,d}$. By the safe-set property, there is no path from $c$ to $d$ in $G_{>t}(A)$. Therefore
$$
B_A(c,d)\le t.
$$
Consequently,
$$
B_A(d,c)\ge t\ge B_A(c,d),
$$
and the lemma in Section 3 shows that $W(A)\ne\{c\}$. Thus every accepted instance has a successful feasible action.
Suppose a feasible action $S$ succeeds, and write
$$
A=C\cup S.
$$
By Section 3, some $d_0\in A\setminus\{c\}$ satisfies
$$
B_A(d_0,c)\ge B_A(c,d_0).
$$
Set
$$
t=B_A(d_0,c).
$$
Choose a simple path $P$ from $d_0$ to $c$ attaining this value. Its minimum edge weight is $t$, so $t\in\mathcal T$, and every edge of $P$ has weight at least $t$.
Let
$$
H=
\{v\in A:
v\text{ is reachable from }c
\text{ in }G_{>t}(A)\}.
$$
We have $c\in H$. On the other hand, $d_0\notin H$, because otherwise
$$
B_A(c,d_0)>t=B_A(d_0,c),
$$
contradicting the choice of $d_0$.
Travel along $P$ from $d_0$ toward $c$, and let $d$ be the last vertex outside $H$. Let $P^\star$ be the suffix of $P$ beginning at $d$. Every vertex of $P^\star$ after $d$ belongs to $H$.
We prove that the algorithm accepts at the pair $(t,d)$.
First, $C\cup\{d\}\subseteq A$. If $c$ belonged to $R_{t,d}$, the corresponding path within $C\cup\{d\}$ would also be present in $A$, putting $d$ in $H$. Therefore
$$
c\notin R_{t,d}.
$$
This pair is not discarded.
Next, consider any additional alternative $x$ on $P^\star$ other than $d$. Then $x\in H$. Suppose there were $r\in R_{t,d}$ with
$$
D(x,r)>t.
$$
There would then be:
Their concatenation establishes reachability from $c$ to $d$ in $G_{>t}(A)$, contradicting $d\notin H$. Hence
$$
D(x,r)\le t
\text{ for every }r\in R_{t,d},
$$
so $x\in E_{t,d}$.
All old alternatives are included in $V_{t,d}$, as is $d$. Thus the entire suffix $P^\star$ lies in $V_{t,d}$. Its edges have weight at least $t$, and its number of additional alternatives is at most
$$
|S|\le k.
$$
The shortest-path calculation therefore finds cost at most $k$.
This proves completeness.
After the preprocessing of Section 2, each threshold and opponent pair requires:
Each operation takes $O(m^2h)$ bit operations. For the shortest-path computation, ordinary Dijkstra with linear scanning suffices; finite relevant distances are at most $m$.
There are $O(m^2)$ thresholds and at most $m-1$ opponents. Hence destructive Schulze addition is decidable in
$$
O\!\left(
\tau L^2+\tau m^2L+m^2Lh+m^5h
\right)
$$
bit operations.
There is no exponential dependence on $k$. Indeed, minimizing the path cost over all processed pairs computes the minimum number of additions needed for destructive success; the algorithm then compares that minimum with $k$.
For the other three combinations, exact enumeration gives explicit upper bounds. Put
$$
H_k=\sum_{j=0}^{k}\binom{|C'|}{j}.
$$
Then the running times are
$$
O(T_{\mathrm{pre}}+H_km^3h)
$$
for constructive Schulze addition, and
$$
O(T_{\mathrm{pre}}+H_km^4h)
$$
for either ranked-pairs mode.
Since
$$
H_k\le(k+1)m^k,
$$
all combinations are polynomial-time solvable for fixed $k$. The hardness classifications concern unrestricted input quota.
The known theorem used here is that, with explicitly listed unweighted strict-ranking voters, constructive alternative addition is $\mathrm{NP}$-hard for Schulze and ranked pairs, and destructive alternative addition is $\mathrm{NP}$-hard for ranked pairs. Its Schulze objective is unique victory; its ranked-pairs results apply to any fixed tie-breaking mechanism. The paper explicitly permits negative Schulze path weights and defines the same addition quota and destructive objective used here. [Parkes–Xia, Theorem 3 and definitions](https://cdn.aaai.org/ojs/8258/8258-13-11786-1-2-20201228.pdf)
To transfer this theorem, take an explicitly listed electorate with $n\ge1$ voters. Group identical rankings. If ranking $R$ occurs $t_R$ times, give it mass
$$
\mu(R)=\frac{t_R}{n}.
$$
This transformation is polynomial-time: there are at most $n$ support rankings, and each numerator and denominator has $O(\log(n+1))$ bits. For every pair,
$$
D_{\mathrm{support}}(a,b)
=
\frac{D_{\mathrm{unweighted}}(a,b)}{n}.
$$
For Schulze, positive scaling multiplies every path strength and strongest-path value by the same factor, preserving the entire winner set.
For ranked pairs, positive scaling preserves the complete edge order, including ties. Labels are unchanged. Induction over the processed edges therefore preserves the locked graph and its source.
Both statements hold for every retained set $C\cup S$. Consequently, the transformation preserves success of every feasible action, in either mode.
The three cited hardness results therefore apply to the rational-support model. Together with the $\mathrm{NP}$ membership proved in Section 2, they establish the three $\mathrm{NP}$-completeness entries in the table.
For completeness, the reverse transformation from the notes also holds, with the all-zero case made explicit.
Use the compressed even antisymmetric matrix $F$ from Section 2. For an unordered pair oriented so that
$$
F(a,b)=2j>0,
$$
list the remaining alternatives as $r_1,\ldots,r_{m-2}$. Introduce $j$ copies of each ranking
$$
a\succ b\succ r_1\succ\cdots\succ r_{m-2}
$$
and
$$
r_{m-2}\succ\cdots\succ r_1\succ a\succ b.
$$
One pair of these rankings contributes margin $2$ to $a$ against $b$. Every other contribution cancels: the remaining alternatives reverse their mutual order, and each is below $a,b$ in one ranking and above them in the other.
Summing these gadgets realizes exactly $F$. Write $u=\binom m2$. If $F$ is nonzero, the actual number of constructed voters is
$$
n_F=
\sum_{\{a,b\}\subseteq U}|F(a,b)|
\le 2u^2.
$$
If $F$ is identically zero, instead use an arbitrary ranking and its reverse, and explicitly set
$$
n_F=2.
$$
This includes $m=1$.
Thus the electorate has polynomial size, with encoding length
$$
O(m^5h),
$$
and construction time
$$
O(T_{\mathrm{pre}}+m^5h).
$$
Section 2 proved that $F$ preserves both rules on every retained set. Keeping $C,C',c,k$, the rule, and the mode unchanged therefore gives a polynomial-time many-one reduction back to explicitly listed unweighted elections.
Accordingly, the classification above also applies to the corresponding unweighted problems. In particular, the destructive Schulze algorithm does not rely on rational masses or support compression.
⟨structured verdict parsed — rendered above⟩
The prover’s classification is correct for the rules and success conditions in USER_TASK. The destructive Schulze algorithm has a valid soundness and completeness proof, and the three hardness transfers satisfy the cited theorem’s hypotheses. I found no major or minor mathematical issues requiring repair.
| Rule | Constructive addition | Destructive addition |
|---|---|---|
| Schulze | $\mathrm{NP}$-complete | $\mathrm{P}$ |
| Ranked pairs | $\mathrm{NP}$-complete | $\mathrm{NP}$-complete |
The common-denominator construction is correct. Since each mass is positive and the masses sum to $1$, the resulting integers satisfy
$$
w_i>0,\qquad \sum_i w_i=Q.
$$
Consequently, $w_i\le Q$ and $|M(a,b)|\le Q$. The product defining $Q$ has bit length bounded by the sum of the input denominator bit lengths, so all these integers have $O(L)$ bits.
Restriction preserves every comparison between retained alternatives. Thus the same margin matrix correctly represents every feasible action.
The preprocessing bound
$$
O(\tau L^2+\tau m^2L+m^2Lh)
$$
is conservative and valid: common-denominator arithmetic fits the first term, accumulation of pairwise margins fits the second, and sorting $O(m^2)$ integer margins using $O(L)$-bit comparisons fits the third.
The map $f$ is strictly increasing on every occurring edge weight and preserves antisymmetry. Both the minimum along a path and the maximum over the finite collection of simple paths therefore commute with $f$.
This establishes preservation of all Schulze comparisons, including ties, on every retained set. For ranked pairs, preservation of weight order and equality classes, together with unchanged labels, preserves the complete processing order and every locking decision.
Compressed weights require $O(h)$ bits because their magnitudes are at most $2\binom m2$.
The Schulze verification procedure is valid with zero and negative weights. The formal diagonal value $+\infty$ is appropriate for empty paths. Cycle deletion cannot decrease a walk’s bottleneck, so the max–min recurrence computes the specified simple-path strengths for distinct endpoints.
The bound $O(m^3h)$ follows from the number of updates and the compressed weight size.
For ranked pairs, an insertion creates a cycle exactly when the proposed target already reaches the proposed source. Maintaining transitive closure gives the stated conservative bound $O(m^4h)$.
The unique-source argument is also correct. After all ordered pairs have been processed, every pair of distinct alternatives is comparable by reachability: accepting an edge establishes forward reachability, while rejection requires existing reverse reachability. The final graph remains acyclic, and comparability excludes two distinct sources.
A certificate naming at most $k$ additions has $O(kh)$ bits after indexing alternatives. Checking feasibility and computing the winner set takes polynomial time. All four problems therefore belong to $\mathrm{NP}$.
The lemma in Section 3 is proved correctly.
The bottleneck inequality follows from concatenation and cycle removal. In the transitivity argument, the cases $x\le y$ and $y\le x$ exhaust all possibilities, including equality. In each case, the hypothesis
$$
t\ge\min\{x,y\}
$$
contradicts one of the assumed strict comparisons. Therefore strict path dominance is transitive and asymmetric.
The finite-relation argument is sufficient: following incoming dominators terminates, and transitivity makes the terminal undominated vertex dominate the initial vertex. Consequently, a sole undominated vertex must strictly dominate every other vertex.
The negation used by the algorithm is thus justified:
$$
W(A)\ne\{c\}
\quad\Longleftrightarrow\quad
\exists d\ne c:\ B_A(d,c)\ge B_A(c,d).
$$
It correctly covers both multiple-winner outcomes containing $c$ and outcomes in which $c$ is not a winner. The singleton retained set satisfies the original lemma vacuously.
For distinct endpoints, the stated strict and weak threshold equivalences hold. There are finitely many simple paths, their bottlenecks are attained, and threshold reachability can be represented by a simple path through cycle deletion.
Allowing length-zero reachability correctly ensures $d\in R_{t,d}$ and $c\in H$.
The proof checks every possible edge entering $R_{t,d}$ from its complement:
Since $c\notin R_{t,d}$ and $d\in R_{t,d}$, the claimed absence of a strict-threshold path from $c$ to $d$ follows.
The initial charge counts $d$ when it is an addition, and each edge charges its destination when that destination is an addition. For a simple path, this counts each selected additional alternative exactly once.
The costs are nonnegative. Removing cycles cannot increase cost, so shortest-walk optimization yields the required minimum simple-path cost. The hypotheses for the cited shortest-path method are satisfied.
For an accepted path, the selected action contains exactly its additional vertices and respects the quota. Its edges establish
$$
B_A(d,c)\ge t.
$$
Because the retained set is contained in the safe set, it has no strict-threshold path from $c$ to $d$, giving
$$
B_A(c,d)\le t.
$$
The unique-winner criterion then establishes destructive success. No additional assumption is needed.
This is the decisive part of the proof, and every step is justified.
The successful action supplies an opponent $d_0$ satisfying the non-strict reverse comparison. Its strongest-path value $t$ is an occurring edge weight, so the algorithm enumerates it.
The set $H$ contains $c$ and excludes $d_0$. Hence the witnessing path has a last vertex $d$ outside $H$, and $d\ne c$. Every later vertex of its suffix belongs to $H$.
The pair $(t,d)$ cannot be discarded: a strict-threshold path from $c$ to $d$ inside $C\cup\{d\}$ would also exist inside the successful retained set.
For every later additional vertex $x$, the proposed forbidden edge into $R_{t,d}$ would concatenate with the specified paths to make $d$ reachable from $c$ above threshold $t$. This contradicts $d\notin H$. Therefore every such $x$ belongs to $E_{t,d}$.
The suffix consequently lies entirely in the algorithm’s allowable set, meets the threshold, and uses at most $|S|\le k$ additions. The algorithm accepts. There is no completeness gap.
There are $O(m^2)$ thresholds and at most $m-1$ opponents. Reverse reachability, allowable-set construction, and dense shortest-path computation each fit $O(m^2h)$ per pair. Finite shortest-path costs are at most $m$ because a simple path contains at most $m$ vertices.
The resulting bound
$$
O(\tau L^2+\tau m^2L+m^2Lh+m^5h)
$$
is valid.
The enumeration bounds for the other modes also hold. The estimate
$$
\sum_{j=0}^{k}\binom{|C'|}{j}\le(k+1)m^k
$$
covers $k=0$, so the fixed-quota polynomial-time claim is correct.
The write-up handles $m=1$ explicitly. Empty addition sets, quota zero, all-zero margins, and negative thresholds cause no failure in the argument.
The cited theorem matches the necessary hypotheses. Parkes–Xia’s Theorem 3 establishes the three claimed addition-control hardness results. Their definitions use unique victory for Schulze, the quota “at most,” and failure of unique victory for destruction; their ranked-pairs results apply to arbitrary fixed tie-breaking. Their Schulze definition explicitly allows negative path weights. [Parkes–Xia, definitions and Theorem 3](https://cdn.aaai.org/ojs/8258/8258-13-11786-1-2-20201228.pdf)
Grouping identical unweighted rankings and assigning mass $t_R/n$ is polynomial in the explicitly listed electorate’s encoding length. It scales every margin by the same positive factor. This preserves Schulze comparisons and ranked-pairs processing, including ties, for every feasible retained set.
Thus the transfers establish all three hardness claims. Together with membership in $\mathrm{NP}$, they establish the three completeness claims.
The historical statement about destructive Schulze addition being open in both winner models is also accurately attributed to the cited conclusion. That statement does not invalidate the independently supplied algorithm. [Maushagen et al., Section 6](https://www.ijcai.org/proceedings/2024/0326.pdf)
The two-ranking gadget contributes margin $2$ to its designated pair and cancels every other pairwise contribution. Repeating and summing the gadgets therefore realizes exactly $F$.
Writing $u=\binom m2$, each magnitude is at most $2u$, and there are at most $u$ contributing pairs. Hence
$$
n_F=\sum_{\{a,b\}}|F(a,b)|\le 2u^2.
$$
The stated encoding and construction bounds follow.
The all-zero case is correctly handled by a ranking and its reverse, including $m=1$. Preservation on all retained subsets was already established in Section 2, so the reverse reduction is justified.
No additional clarification or missing lemma is required. The direction is fully verified as written.
⟨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.