Answer: \(\mathrm{NP}\)-hard under polynomial-time many-one reductions; indeed \(\Theta_2^p\)-hard even for \(k=1\).
Theorem 2.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor each of Dodgson elections, Kemeny elections, and Young elections, the following control problems are $\Theta_{2}^{p}$-hard: constructive control by adding candidates, constructive control by deleting candidates, constructive control by adding voters, and constructive control by deleting voters.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate set \(C\), target \(c\in C\), deletion budget \(k\), and rational distribution \(\mu\) over complete rankings of \(C\), does there exist \(D\subseteq C\setminus\{c\)\) with \(|D|\le k\) such that \(c\) is the unique Kemeny winner after restricting all rankings to \(C\setminus D\)?
Given a candidate set \(C\) with \(m=|C|\ge 2\), a distinguished candidate \(c\in C\), and a binary integer budget \(1\le k<m\), consider constructive control by deleting candidates.
A society is given by its support: a list of \(\tau\) distinct strict complete rankings of \(C\), each with positive binary rational mass, 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\).
A legal action deletes an indivisible set \(D\subseteq C\setminus\{c\}\) with \(|D|\le k\). Restrict each ranking to \(S=C\setminus D\), preserving its mass and combining identical restricted rankings.
Use the mass-weighted Kemeny rule: optimal rankings minimize expected Kendall tau distance to the restricted society. Its winners are the candidates appearing first in some optimal ranking; thus \(c\) is the unique winner exactly when every optimal ranking starts with \(c\). Apply no tie-breaking.
Is deciding whether some legal deletion makes \(c\) the unique Kemeny winner solvable in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard under polynomial-time many-one reductions?
For explicitly listed finite unweighted electorates, constructive control by deleting candidates is \(\Theta_2^p\)-hard; testing whether a candidate is the unique Kemeny winner is \(\Theta_2^p\)-complete.
The problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. In fact, it is \(\Theta_2^p\)-hard even when \(k=1\).
The proof uses the unique-Kemeny-winner hardness theorem supplied in the question. The unique-winner hardness is also recorded in [*Bypassing Combinatorial Protections*](https://pub.dss.in.tum.de/brandt-research/sp2_journal.pdf). No assumption about the winner convention of the supplied control-hardness theorem is needed.
Let an explicitly listed unweighted electorate consist of \(N\geq1\) rankings \(v_1,\ldots,v_N\) of a candidate set \(A\). Let its distinct rankings be \(\rho_1,\ldots,\rho_\tau\), with multiplicities \(n_1,\ldots,n_\tau\).
Assign \(\rho_i\) mass \(\mu_i=n_i/N\). These masses are positive binary rationals and satisfy \(\sum_i\mu_i=1\).
For any surviving set \(S\subseteq A\) and any ranking \(\pi\) of \(S\), its expected Kendall distance is
\[ \sum_{i=1}^{\tau}\mu_i\,d_{\mathrm{KT}}(\pi,\rho_i|_S) = \frac1N\sum_{j=1}^{N}d_{\mathrm{KT}}(\pi,v_j|_S). \]
Thus normalization multiplies every objective value by the same positive factor \(1/N\). Consequently, it preserves exactly the optimal rankings and their possible first candidates. Combining identical restricted rankings also preserves this sum, by adding their masses.
Lemma. Suppose a candidate \(d\) is first in every ranking of a society of total mass \(1\). For every surviving candidate set containing \(d\), every optimal Kemeny ranking starts with \(d\).
Proof. Consider a ranking \(\pi\) in which \(t\geq1\) candidates precede \(d\). Move \(d\) to first position while preserving the relative order of all other candidates.
Only the \(t\) pairs involving \(d\) and these preceding candidates change. Every support ranking prefers \(d\) in each such pair. Therefore, the move reduces the Kendall distance to every support ranking by exactly \(t\), and reduces expected distance by \(t\sum_i\mu_i=t>0\).
Hence \(\pi\) cannot be optimal. This proves the lemma. \(\square\)
Take an instance \((A,v_1,\ldots,v_N,c)\) of unique-Kemeny-winner testing for explicitly listed unweighted electorates. Write \(n=|A|\).
Construct the target instance as follows:
The output satisfies \(m=n+1\geq2\) and \(1=k<m\).
If a legal deletion retains \(d\), the lemma implies that every optimal ranking starts with \(d\). Since \(c\neq d\), that deletion cannot succeed.
A successful deletion must therefore contain \(d\). Because the budget is \(1\), its deletion set must be exactly \(\{d\}\). After this deletion, the society is precisely the normalized original electorate. Section 1 then gives
\[ \text{the constructed instance admits a successful deletion} \quad\Longleftrightarrow\quad c\text{ is the unique Kemeny winner of the original electorate}. \]
This establishes both directions of the reduction, including all ties.
For completeness, allowing empty electorates in the source convention causes no difficulty: their unique-winner question is immediately decidable, so they can be mapped directly to fixed valid yes- or no-instances.
Encoding size and construction time. The output support has \(\tau\leq N\) distinct rankings. Each mass \(n_i/N\) requires \(O(\log(N+1))\) bits, including numerator and denominator. With candidates encoded by integer identifiers, the output length is
\[ L=O\!\left(\tau m\log(m+1)+\tau\log(N+1)+\log(m+1)\right). \]
Grouping can be performed by sorting the explicitly listed rankings. Comparisons inspect at most \(m\) candidate identifiers; counting multiplicities and reducing the fractions also take polynomial time. Therefore the construction is polynomial in the source input length.
By the supplied \(\Theta_2^p\)-hardness of unique-winner testing, the target problem is \(\Theta_2^p\)-hard. Since \(\mathrm{NP}\subseteq\Theta_2^p\), it is \(\mathrm{NP}\)-hard. A polynomial-time algorithm would consequently imply \(\mathrm{P}=\mathrm{NP}\).
The following upper bound makes the dependence on \(m,\tau,L,k\) explicit.
Write the input masses as \(\mu_i=a_i/b_i\). Set \(Q=\prod_i b_i\) and \(A_i=a_iQ/b_i\). Then \(\sum_iA_i=Q\), and these integers have \(O(L)\) bits.
For distinct candidates \(x,y\), define
\[ w_{xy}=\sum_{\{i:\,y\text{ precedes }x\text{ in }\rho_i\}}A_i. \]
For any ranking, its expected Kendall distance multiplied by \(Q\) equals the sum of \(w_{xy}\) over pairs for which it places \(x\) before \(y\). Restriction to a surviving set preserves these pairwise weights.
For every \(T\subseteq C\), let \(F(T)\) be the minimum scaled cost of a ranking of \(T\). The recurrence is
\[ F(\varnothing)=0,\qquad F(T)=\min_{x\in T}\left(F(T\setminus\{x\})+ \sum_{y\in T\setminus\{x\}}w_{xy}\right). \]
Indeed, fixing \(x\) first fixes every pair involving \(x\), and leaves an independent optimum on \(T\setminus\{x\}\).
Precompute \(H_x(U)=\sum_{y\in U\setminus\{x\}}w_{xy}\) by subset recurrences. This requires \(O(m2^m)\) integer additions. The recurrence for \(F\) then requires \(O(m2^m)\) additions and comparisons.
For a surviving set \(S\) and \(x\in S\), define
\[ G_x(S)=F(S\setminus\{x\})+H_x(S\setminus\{x\}). \]
This is exactly the minimum cost among rankings starting with \(x\). Therefore \(c\) is the unique winner precisely when
\[ G_c(S)<G_x(S)\qquad\text{for every }x\in S\setminus\{c\}. \]
Check this condition for every legal deletion set. Their number is
\[ B(m,k)=\sum_{j=0}^{k}\binom{m-1}{j}. \]
All costs are at most \(Q\binom m2\), so they use \(O(L+\log(m+1))\) bits. A conservative bit-operation bound, including rational preprocessing, is
\[ O\!\left( \bigl(\tau m^2+m2^m+mB(m,k)\bigr) \bigl(L+\log(m+1)\bigr)^2 \right). \]
Thus the problem has an exact algorithm with polynomial dependence on the support size and rational encoding length, but the hardness already holds for the constant budget \(k=1\).
⟨structured verdict parsed — rendered above⟩
The claimed result is proved: the reduction establishes \(\Theta_2^p\)-hardness, and hence \(\mathrm{NP}\)-hardness, under polynomial-time many-one reductions, even with \(k=1\). The exact algorithm and its stated conservative running-time bound are also valid. I found no major or minor mathematical issues.
The prover uses the supplied theorem that unique-Kemeny-winner testing for explicitly listed finite unweighted electorates is \(\Theta_2^p\)-complete. Its source question concerns uniqueness of the winning candidate, exactly as required here; it does not require uniqueness of the optimal ranking.
The additional citation accurately records hardness for the unique-winner version in its discussion following Theorem 5.5. The proof can rely directly on the premise supplied in USER_TASK. [*Bypassing Combinatorial Protections*, page 465](https://pub.dss.in.tum.de/brandt-research/sp2_journal.pdf).
For \(N\geq1\), each multiplicity \(n_i\) is positive, so the assigned mass \(n_i/N\) is a valid positive binary-encoded rational. The masses sum to \(1\).
The displayed identity correctly equates the weighted objective with \(1/N\) times the original total distance, for every surviving set and every ranking of that set. Multiplication by a common positive constant preserves all minimizers, including ties.
Combining identical restricted rankings preserves the objective because their contributions differ only in their masses. Consequently, possible first candidates and unique-winner status are preserved.
If \(t\geq1\) candidates precede \(d\), moving \(d\) first reverses exactly those \(t\) pairs and preserves every other pair.
Every support ranking places \(d\) above each affected candidate. Each reversed pair therefore removes one disagreement from every distance. The expected improvement is exactly \(t\), since total mass is \(1\).
This improvement is strictly positive, excluding every ranking that does not start with \(d\). The argument remains applicable after arbitrary deletions retaining \(d\): restriction preserves the unanimous comparisons involving \(d\). If \(d\) is the sole survivor, the assertion is immediate.
The distinguished source candidate ensures \(n\geq1\). Thus \(m=n+1\geq2\), and \(k=1\) satisfies \(1\leq k<m\).
The new candidate is fresh, so \(d\neq c\), and deleting \(d\) is legal. Prefixing rankings with \(d\) preserves their strictness and completeness. Grouping produces distinct support rankings with positive masses summing to \(1\).
The construction uses indivisible candidate deletions exactly as prescribed.
Every legal deletion retaining \(d\) leaves \(d\) first in every optimal ranking, so it cannot make \(c\) the unique winner. This excludes both the empty deletion and deletion of any original candidate.
Any successful deletion must contain \(d\). With budget \(1\), it must therefore be exactly \(\{d\}\). Following that deletion, the weighted society is the normalized original electorate.
Hence success is equivalent to original unique-winner status. Original ties remain ties after normalization, so the reduction introduces no implicit tie-breaking.
Because voters are explicitly listed, \(N\) is bounded by the source input length up to its encoding overhead. The output has \(\tau\leq N\) rankings, each of length \(m\), and each numerator and denominator requires \(O(\log(N+1))\) bits.
The stated output-size estimate is valid under the specified integer-identifier encoding. Sorting rankings, counting multiplicities, and reducing fractions all take polynomial time.
The optional discussion of empty source electorates does not affect the reduction’s substantive argument: those cases are immediately decidable, and the stated handling is routine.
Composing this reduction with the supplied source hardness establishes \(\Theta_2^p\)-hardness. The inclusion \(\mathrm{NP}\subseteq\Theta_2^p\) then gives \(\mathrm{NP}\)-hardness.
The statement that a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\) is correct. The prover does not claim an unconditional separation from \(\mathrm{P}\), or membership in \(\mathrm{NP}\).
The denominator product \(Q\) and integer weights \(A_i\) are well-defined, with \(\sum_i A_i=Q\). Their bit lengths are \(O(L)\), since the sum of the input denominator bit lengths bounds the product’s bit length.
The orientation of \(w_{xy}\) is correct: when an output ranking places \(x\) before \(y\), disagreements come from support rankings placing \(y\) before \(x\). Restriction preserves these comparisons.
The recurrence for \(F\) correctly partitions rankings according to their first candidate. Its empty-set base case is valid. The subset sums \(H_x\) supply exactly the pair costs required by that recurrence.
Likewise, \(G_x(S)\) is the minimum cost conditional on first candidate \(x\). The strict comparisons against every other survivor therefore characterize the specified unique-winner condition. For a singleton surviving set, the condition is vacuous and correctly accepts \(c\).
There are exactly
\(\sum_{j=0}^{k}\binom{m-1}{j}\)
legal deletion sets. Checking each requires at most \(O(m)\) candidate comparisons.
Pairwise-weight preprocessing, subset-sum computation, and the dynamic program have the stated operation counts. Every cost is at most \(Q\binom{m}{2}\), giving \(O(L+\log(m+1))\) bits. The squared bit-length factor conservatively covers the required exact arithmetic, including rational preprocessing.
Thus the displayed bound correctly states dependence on \(m,\tau,L,k\). Its exponential dependence on \(m\) is consistent with the hardness result.
No repair or additional mathematical clarification is needed.
⟨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.