Answer: \(\mathrm{NP}\)-complete and fixed-parameter tractable parameterized by \(k\), with deterministic running time \(2^{O(k)}\operatorname{poly}(m,\tau,L)\).
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximatek-LSFKOA can be solved in time 2O( √ k log k)n log n. Our other application stems from graph-drawing and the problem itself is called k-ONE SIDED CROSS MINIMIZA- TION (k-OSCM).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a current ranking \(\pi\), an integer \(k\), and a finite-support distribution \(\mu\) over rankings of \(C\) with binary-rational masses summing to \(1\), decide whether there is a ranking \(\sigma\) such that \(D_\mu(\sigma)<D_\mu(\pi)\), \(|L_\mu(\pi)\setminus L_\mu(\sigma)|\le k\), and \(|L_\mu(\sigma)\setminus L_\mu(\pi)|\le k\). Here \(D_\mu(\rho)=\sum_t\mu_t d_K(\rho,t)\), and \(L_\mu(\rho)\) contains the candidate pairs on which at least one positive-mass type disagrees with \(\rho\).
Let \(C\) contain \(m\ge 1\) candidates; all rankings are strict total orders. Write \(a\prec_\rho b\) when \(a\) precedes \(b\) in \(\rho\).
A society is given by its support: \(\tau\) distinct ranking types \(t\) with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length.
Define \(D_\mu(\rho)=\sum_t\mu_t d_K(\rho,t)\), where \(d_K\) is Kendall tau distance, and \(L_\mu(\rho)=\{(a,b)\in C^2:a\ne b,\ b\prec_\rho a,\ \exists t\in\operatorname{supp}(\mu)\text{ with }a\prec_t b\}\). These are ordered pairs, each counted once regardless of its supporting mass.
Given this society, a current ranking \(\pi\), and a binary-encoded integer \(k\ge 0\), decide whether some ranking \(\sigma\) satisfies \(D_\mu(\sigma)<D_\mu(\pi)\), \(|L_\mu(\pi)\setminus L_\mu(\sigma)|\le k\), and \(|L_\mu(\sigma)\setminus L_\mu(\pi)|\le k\).
Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? If it is \(\mathrm{NP}\)-hard, is it FPT parameterized by \(k\), with running time \(f(k)\operatorname{poly}(m,\tau,L)\)?
For explicit finite electorates, the same local-search problem has a claimed deterministic \(2^{O(\sqrt{k}\log(k+2))}m\log(m+1)\) algorithm, apart from input processing and arithmetic costs. [Fomin et al.](https://sites.cs.ucsb.edu/~daniello/papers/FastLocalSearch.pdf)
For finite electorates, unrestricted strict improvement is \(\mathrm{NP}\)-complete, as the complement of Kemeny Consensus Recognition. [Fitzsimmons and Hemaspaandra](https://arxiv.org/pdf/2105.08540)
No result specifically treating the support-encoded rational-mass problem above was located.
The problem is \(\mathrm{NP}\)-complete and is fixed-parameter tractable parameterized by \(k\). A deterministic algorithm runs in time \(2^{O(k)}\operatorname{poly}(m,\tau,L)\).
The FPT proof below is self-contained; it does not require extending the cited finite-electorate algorithm.
For distinct candidates \(a,b\), define
\(\displaystyle p(a,b)=\sum_{t:a\prec_t b}\mu_t.\)
Because every supported ranking is a strict total order and the masses sum to \(1\),
\(\displaystyle p(a,b)+p(b,a)=1.\)
Moreover, positivity of every supported mass gives
\(\displaystyle p(a,b)>0\quad\Longleftrightarrow\quad \exists t\in\operatorname{supp}(\mu)\text{ with }a\prec_t b.\)
Write each mass as \(\mu_t=\alpha_t/\beta_t\), with positive integers \(\alpha_t,\beta_t\). Set
\(\displaystyle Q=\prod_t\beta_t,\qquad w_t=\alpha_t(Q/\beta_t),\qquad W(a,b)=\sum_{t:a\prec_t b}w_t.\)
Then \(W(a,b)=Qp(a,b)\), and \(W(a,b)+W(b,a)=Q\). The binary length of \(Q\) is at most the sum of the denominator lengths, hence \(O(L)\). All these integers can therefore be computed in polynomial time without expanding an electorate.
For a ranking \(\rho=(x_1,\ldots,x_m)\), define its integer score
\(\displaystyle E(\rho)=\sum_{1\le i<j\le m}W(x_j,x_i).\)
For each unordered pair, the summand is precisely the total integer mass of supported rankings that disagree with \(\rho\). Consequently,
\(\displaystyle E(\rho)=QD_\mu(\rho).\)
Thus strict improvement is equivalent to \(E(\sigma)<E(\pi)\). Every score is at most \(Q\binom m2\), so its binary length is \(O(L+\log(m+1))\).
A proposed ranking \(\sigma\) is a polynomial-size certificate. Its score and both set-difference cardinalities can be computed exactly in polynomial time. The problem is therefore in \(\mathrm{NP}\).
We use the established theorem that Kemeny Consensus Recognition for explicit finite electorates is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions. Its complement asks whether a given ranking has a strictly better ranking and is therefore \(\mathrm{NP}\)-complete. See Theorem 5 of [Fitzsimmons and Hemaspaandra](https://arxiv.org/pdf/2105.08540).
Consider an instance of that complement problem with candidates \(C\), current ranking \(\pi\), and an explicit nonempty electorate \(v_1,\ldots,v_n\). Write
\(\displaystyle S(\rho)=\sum_{i=1}^n d_K(\rho,v_i),\qquad N=\binom m2.\)
The following construction works even if “binary-rational” is interpreted as requiring dyadic masses.
Let \(M\) be the smallest power of two satisfying \(M\ge 2n\). Duplicate every original voter. Choose any ranking \(\eta\), let \(\eta^{\mathrm{rev}}\) be its reversal, and add
\(\displaystyle h=(M-2n)/2\)
copies of each of \(\eta\) and \(\eta^{\mathrm{rev}}\). This creates exactly \(M\) voters. The integer \(h\) is nonnegative because \(M\) and \(2n\) are even.
For every ranking \(\rho\),
\(\displaystyle d_K(\rho,\eta)+d_K(\rho,\eta^{\mathrm{rev}})=N,\)
since on each unordered pair exactly one of these two rankings disagrees with \(\rho\). Hence the new electorate’s total score is
\(\displaystyle 2S(\rho)+hN.\)
Compress identical rankings into distinct types, assigning each type its multiplicity divided by \(M\). These masses are positive dyadic rationals and sum to \(1\). For the resulting society,
\(\displaystyle D_\mu(\rho)=\frac{2S(\rho)+hN}{M}.\)
It follows that \(D_\mu(\sigma)<D_\mu(\pi)\) if and only if \(S(\sigma)<S(\pi)\).
Set the output parameter to \(k=N\). For any ranking \(\rho\), the set \(L_\mu(\rho)\) contains at most one ordered pair for each unordered candidate pair: only the orientation opposed to \(\rho\) can belong to it. Therefore \(|L_\mu(\rho)|\le N\), and both exchange constraints are automatically satisfied.
The construction is polynomial: \(M<4n\), and compression and mass encoding take polynomial time. It is a many-one reduction from unrestricted strict improvement. Together with membership in \(\mathrm{NP}\), this proves \(\mathrm{NP}\)-completeness.
For two rankings, write
\(\displaystyle R(\pi,\sigma)=|L_\mu(\pi)\setminus L_\mu(\sigma)|,\qquad A(\pi,\sigma)=|L_\mu(\sigma)\setminus L_\mu(\pi)|.\)
Consider an unordered pair on which \(\pi\) and \(\sigma\) disagree. Name its candidates so that \(a\prec_\pi b\) and \(b\prec_\sigma a\).
Under \(\pi\), the only possible element of \(L_\mu(\pi)\) belonging to this pair is \((b,a)\), present exactly when \(W(b,a)>0\). Under \(\sigma\), the only possible element is \((a,b)\), present exactly when \(W(a,b)>0\). Thus this reversal contributes
\(\displaystyle \mathbf 1[W(b,a)>0]\quad\text{to }R(\pi,\sigma),\)
and
\(\displaystyle \mathbf 1[W(a,b)>0]\quad\text{to }A(\pi,\sigma).\)
At least one contribution is \(1\), because \(W(a,b)+W(b,a)=Q>0\). Pairs with unchanged orientation contribute nothing. Summing over all pairs proves
\(\displaystyle d_K(\pi,\sigma)\le R(\pi,\sigma)+A(\pi,\sigma).\)
Every feasible ranking consequently satisfies
\(\displaystyle d_K(\pi,\sigma)\le 2k.\)
This bound concerns candidate pairs, independently of their masses.
Set \(K=\min\{k,N\}\). Replacing \(k\) by \(K\) preserves the problem because each exchange cardinality is at most \(N\). Let \(r=2K\), and write
\(\displaystyle \pi=(c_1,\ldots,c_m).\)
We first prove that Kendall distance at most \(r\) implies displacement at most \(r\) for every candidate.
Suppose \(c_j\) occupies position \(p\) in \(\sigma\).
Thus \(|p-j|\le d_K(\pi,\sigma)\le r\).
Now let \(S_i\) be the set of the first \(i\) candidates of a feasible \(\sigma\). Displacement gives two necessary conditions:
Define
\(\displaystyle P_i=\{c_j:1\le j\le \max(0,i-r)\},\)
and
\(\displaystyle B_i=\{c_j:\max(1,i-r+1)\le j\le \min(m,i+r)\}.\)
Call a set \(S\) admissible at layer \(i\) when
\(\displaystyle |S|=i,\qquad P_i\subseteq S\subseteq P_i\cup B_i.\)
Every feasible ranking has an admissible prefix set at every layer. Since \(|B_i|\le 2r=4K\), there are at most \(2^{4K}\) admissible sets at each layer.
These conditions need not characterize feasibility exactly. We will enforce the original exchange constraints separately.
For an admissible set \(S\) and integers \(0\le h,\ell\le K\), let \(F(S,h,\ell)\) be the minimum internal score of an ordering of \(S\) with the following properties:
Here the internal score counts only pairs with both endpoints in \(S\). An absent state has value \(+\infty\). Initialize
\(\displaystyle F(\varnothing,0,0)=0.\)
Suppose \(S\) is an admissible set of size \(i\), and append \(x=c_j\notin S\). Allow this transition only when \(T=S\cup\{x\}\) is admissible at layer \(i+1\).
The newly determined pairs are precisely those joining \(x\) to candidates \(u\in S\). Their score contribution is
\(\displaystyle \Delta E(S,x)=\sum_{u\in S}W(x,u),\)
because every such \(u\) precedes \(x\) in the constructed ranking.
A newly determined pair is reversed relative to \(\pi\) exactly when \(u=c_q\) with \(q>j\). By Section 3, the increments are therefore
\(\displaystyle \Delta R(S,x)=\sum_{\substack{c_q\in S\\q>j}}\mathbf 1[W(c_q,x)>0],\)
and
\(\displaystyle \Delta A(S,x)=\sum_{\substack{c_q\in S\\q>j}}\mathbf 1[W(x,c_q)>0].\)
If \(h+\Delta R(S,x)\le K\) and \(\ell+\Delta A(S,x)\le K\), update
\(\displaystyle F(T,h+\Delta R(S,x),\ell+\Delta A(S,x)) =\min\bigl\{F(T,h+\Delta R(S,x),\ell+\Delta A(S,x)),\,F(S,h,\ell)+\Delta E(S,x)\bigr\}.\)
All layers are processed in increasing order of their cardinality.
Each unordered pair is counted exactly once, when its second endpoint is appended. The transition formulas thus give its exact score, removal count, and addition count.
Furthermore, these increments depend only on the set \(S\) and appended candidate \(x\), not on the order previously used inside \(S\). Retaining only the minimum score for each state therefore preserves all possible improvements: any extension available to a discarded ordering is also available to the retained ordering, with identical subsequent increments.
Induction on the layer proves that the dynamic program computes exactly the stated minima. For the induction step, every permitted append constructs an ordering satisfying the state definition. Conversely, removing the last candidate from an ordering satisfying that definition produces its predecessor state and exactly the increments above.
At the final layer, accept precisely when
\(\displaystyle \min_{0\le h,\ell\le K}F(C,h,\ell)<E(\pi).\)
An accepting state reconstructs a full ranking satisfying both original exchange constraints and strict improvement.
Conversely, any feasible improving ranking has admissible prefix sets by Sections 3–4. Its partial exchange counts never exceed its final counts, because every increment is nonnegative. Thus none of its transitions is discarded, and the final minimum is at most its score. The algorithm accepts.
There are at most
\(\displaystyle (m+1)\,2^{4K}(K+1)^2\)
states. Each has at most \(m\) candidate extensions. Each extension and its admissibility check can be evaluated with \(O(m)\) elementary operations.
All score arithmetic uses integers of \(O(L+\log(m+1))\) bits. Computing the pairwise matrix also takes polynomial time in \(m,\tau,L\). The total running time is therefore bounded by
\(\displaystyle 2^{O(k)}\operatorname{poly}(m,\tau,L).\)
This proves deterministic fixed-parameter tractability for the support-encoded rational-mass problem.
⟨structured verdict parsed — rendered above⟩
The prover resolves both questions. The reduction establishes \(\mathrm{NP}\)-completeness for the support-encoded problem, including when masses must be dyadic. The dynamic program establishes deterministic fixed-parameter tractability parameterized by \(k\), with the claimed running time \(2^{O(k)}\operatorname{poly}(m,\tau,L)\).
I found no major or minor mathematical issues. The argument does not establish the sharper finite-electorate running time mentioned in the task, but that bound was not required.
All steps in Section 1 are valid.
For each distinct pair \(a,b\), every supported strict total order places exactly one candidate before the other. Consequently,
\[
p(a,b)+p(b,a)=1.
\]
The equivalence between \(p(a,b)>0\) and the existence of a supported ranking placing \(a\) before \(b\) uses the stipulated positivity of all masses. That hypothesis is present.
The common denominator construction is exact. Each \(\beta_t\) divides \(Q\), so every \(w_t\) is an integer, and
\[
W(a,b)=Qp(a,b).
\]
The bit length of the product \(Q\) is bounded by the sum of the denominator bit lengths. Thus forming this product and the pairwise weights requires polynomial bit complexity; its potentially large numerical value does not require expanding an electorate.
The score formula has the correct orientation: when \(\rho\) places \(x_i\) before \(x_j\), the disagreement mass is \(W(x_j,x_i)\). Therefore,
\[
E(\rho)=QD_\mu(\rho).
\]
Since \(Q>0\), multiplication by \(Q\) preserves strict inequalities.
The bound \(E(\rho)\le Q\binom m2\) yields the stated polynomial score bit length. A certificate consisting of a ranking can be checked for validity, its exact score calculated, and both ordered-pair set differences counted in polynomial time. Membership in \(\mathrm{NP}\) follows.
The external theorem is correctly identified. Theorem 5 of [Fitzsimmons and Hemaspaandra](https://arxiv.org/pdf/2105.08540) states that Kemeny Consensus Recognition is \(\mathrm{coNP}\)-complete. The paper uses strict total-order votes and defines a consensus by minimizing the sum of Kendall distances; it also explicitly identifies polynomial-time many-one reductions as its reduction convention. Its complement is therefore the unrestricted strict-improvement problem used by the prover.
The reduction preserves the required decision predicate.
\[
h=\frac{M-2n}{2}
\]
is a nonnegative integer. The duplicated and added voters total \(2n+2h=M\).
\[
d_K(\rho,\eta)+d_K(\rho,\eta^{\mathrm{rev}})=N.
\]
The padded score is exactly \(2S(\rho)+hN\).
\[
D_\mu(\rho)=\frac{2S(\rho)+hN}{M}
\]
applies to every ranking. The added term is independent of the ranking, and the scaling factor is positive. The stated equivalence of strict-improvement predicates follows.
Together with membership in \(\mathrm{NP}\), this proves the claimed \(\mathrm{NP}\)-completeness.
The pairwise analysis in Section 3 is correct.
For a reversed pair with \(a\prec_\pi b\) and \(b\prec_\sigma a\), the possible element under \(\pi\) is \((b,a)\), whereas the possible element under \(\sigma\) is \((a,b)\). These are different ordered pairs. Their respective membership conditions are exactly \(W(b,a)>0\) and \(W(a,b)>0\).
Thus the stated removal and addition contributions are correct. At least one is positive because
\[
W(a,b)+W(b,a)=Q>0.
\]
An unchanged pair has identical membership under both rankings and contributes nothing to either difference.
Summing establishes
\[
d_K(\pi,\sigma)\le R(\pi,\sigma)+A(\pi,\sigma)\le2k
\]
for every feasible ranking. This reasoning handles unanimous pairs as well as pairs supported in both orientations.
The parameter truncation is valid: both exchange counts are always at most \(N\), so replacing \(k\) by \(K=\min\{k,N\}\) preserves feasibility.
The displacement argument is correct in both directions:
Hence every candidate in a feasible ranking has displacement at most \(r=2K\).
The resulting prefix conditions follow with the correct boundary inequalities. Candidates indexed at most \(i-r\) must already appear in the prefix of length \(i\); candidates indexed strictly above \(i+r\) cannot appear there.
The definitions of \(P_i\) and \(B_i\) implement these conditions, including layers near either endpoint. The window \(B_i\) has at most \(2r=4K\) candidates. An admissible set is determined by its choice of elements from this window, so the bound of \(2^{4K}\) sets per layer is valid.
The prover correctly treats admissibility as a necessary condition, without claiming it characterizes feasibility.
The state records sufficient information for continuation.
Appending \(x\) after all elements of \(S\) determines precisely the pairs joining \(x\) to \(S\). For each \(u\in S\), the constructed order places \(u\) before \(x\), so its score contribution is \(W(x,u)\). The formula for \(\Delta E(S,x)\) is correct.
If \(x=c_j\), such a pair is reversed relative to \(\pi\) exactly when \(u=c_q\) with \(q>j\). For this reversal:
These match Section 3, so both transition count formulas have the correct orientations.
All three increments depend only on \(S\) and \(x\). Future transitions therefore do not need the internal order previously chosen for \(S\). For fixed \(S,h,\ell\), keeping only the smallest internal score is sound.
The stated induction proves the state interpretation:
There is no omitted interaction between internal ordering and later exchange counts.
The acceptance condition checks the original objective and constraints.
An accepting final state represents a complete ranking with removal and addition counts at most \(K\le k\) and score strictly below \(E(\pi)\). The integer-score identity converts this into strict improvement in \(D_\mu\).
Conversely, every feasible improving ranking has admissible prefixes by Sections 3–4. Each partial exchange count is at most its final count because all increments are nonnegative. Consequently, its construction is never discarded by a count bound. Score minimization can only decrease its final score, so the algorithm accepts.
Both directions are established.
The state bound
\[
(m+1)2^{4K}(K+1)^2
\]
is valid. There are at most \(m\) extensions per state, and the score, count increments, and admissibility check can each be evaluated by scanning at most \(m\) candidates.
Admissible sets can be enumerated through the subsets of the stated bounded windows; the state representation therefore requires no enumeration of all candidate subsets.
The factor \((K+1)^2\) is absorbed into \(2^{O(k)}\), since \(K\le k\). Exact arithmetic uses polynomially many bits, as established in Section 1. The total bound is consequently
\[
2^{O(k)}\operatorname{poly}(m,\tau,L).
\]
This is an FPT bound, with no parameter dependence in the polynomial exponent.
The edge cases are also covered:
The proof is correct and rigorous as written. No additional lemma, calculation, hypothesis clarification, or repair is needed. It establishes hardness of the unrestricted support-encoded problem and deterministic FPT solvability with parameter \(k\); these conclusions are compatible.
⟨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.