Answer: All four outputs are exactly computable in time polynomial in \(m,\tau,L\).
Theorem 3.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere are polynomial-time algorithms that given a collection V of voters and a linear order L compute the smallest k such that V is a: (1) k-maverick-SP society with respect to L, (2) Dodgsonk-SP society with respect to L, and (3) PerceptionFlipk-SP society with respect to L. There is also a polynomial-time algorithm that given the same input decides if V is a swoon-SP society. We assume that our requirements regarding nearness to single-peakedness are for all the voters that appear in our problems (both before and after each manipulative action).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a supplied axis \(L\), and a finite distribution \(\mu\) over ranking types, compute the minimum mass that must be removed so every remaining type is single-peaked with respect to \(L\); the maximum, over supported types, of each type’s minimum adjacent-swap distance to a single-peaked ranking and to an axis making it single-peaked; and whether every supported type is swoon-SP.
Given a nonempty candidate set \(C\) with \(m=|C|\), a supplied strict linear axis \(A\), and a probability distribution \(\mu\) over strict rankings of \(C\), consider the following four outputs.
A society is given by its support: the list \(S\) of its \(\tau\) distinct types with positive mass, each mass a binary rational, with \(\sum_{v\in S}\mu(v)=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\).
Write \(\operatorname{SP}(v,A)\) for standard single-peakedness and \(d(u,w)\) for the minimum number of sequential adjacent-candidate swaps transforming one strict order into another.
The deletion output is the minimum \(\sum_{v\in S}r_v\) over removed masses \(0\le r_v\le\mu(v)\), requiring \(\operatorname{SP}(v,A)\) whenever \(\mu(v)-r_v>0\); removing all mass is allowed.
The ranking-swap output is \(D=\max_{v\in S}\min_{v':\operatorname{SP}(v',A)}d(v,v')\), where \(v'\) ranges over strict rankings of \(C\).
The axis-swap output is \(F=\max_{v\in S}\min_{B:\operatorname{SP}(v,B)}d(A,B)\), where \(B\) ranges over strict axes on \(C\) and may differ for each type.
The swoon-SP output asks whether, for every \(v\in S\), deleting its top candidate from both \(v\) and \(A\) leaves a single-peaked ranking; rankings on at most one candidate satisfy this condition.
Can these four outputs be computed exactly in time polynomial in \(m,\tau,L\), or is any component NP-hard?
For explicit finite voter lists and a supplied axis, the corresponding minimum deletion count, both maximum swap distances, and swoon-SP test have polynomial-time algorithms ([source](https://www.ijcai.org/Proceedings/15/Papers/591.pdf)).
No result explicitly treating this rational-mass formulation was located in the search.
All four outputs are exactly computable in time polynomial in \(m,\tau,L\). Rational masses do not require expanding the support into repeated voters.
The supplied-axis definitions agree with those in Theorem 3.3 of the [cited paper](https://www.ijcai.org/Proceedings/15/Papers/591.pdf). Below is a self-contained proof, including explicit algorithms and rational-arithmetic bounds.
Write the axis as \(A=(a_1,\ldots,a_m)\). For a ranking \(v\), let \(\operatorname{pos}_v(x)\) denote the position of candidate \(x\), with position \(1\) most preferred.
A strict ranking with peak \(a_p\) is single-peaked on \(A\) precisely when preference decreases as one moves away from \(a_p\) on either side:
There is no additional constraint comparing candidates on opposite sides of the peak.
Fact 1: Adjacent-swap distance counts disagreeing pairs.
For two strict orders \(u,w\), let \(I(u,w)\) be the number of unordered candidate pairs ordered differently by \(u\) and \(w\). Then \(d(u,w)=I(u,w)\).
Indeed, an adjacent swap changes the relative order of exactly one pair, so at least \(I(u,w)\) swaps are necessary. Conversely, replace each candidate in \(u\) by its position in \(w\). Whenever this sequence is unsorted, it has an adjacent descent. Swapping that descent decreases its inversion count by exactly one. Repeating reaches \(w\) in exactly \(I(u,w)\) swaps.
Fact 2: Single-peaked rankings admit endpoint elimination.
On an axis with at least two candidates, a ranking is single-peaked if and only if its least-preferred candidate is an axis endpoint and its restriction to the remaining candidates is single-peaked on the restricted axis.
For necessity, an internal least-preferred candidate cannot be the peak. If it lies left of the peak, the candidate immediately to its left must be less preferred; if it lies right of the peak, the candidate immediately to its right must be less preferred. Both contradict least-preferredness. Restricting a single-peaked ranking after removing an endpoint preserves the required monotonicity.
For sufficiency, adding a new least-preferred candidate at an axis endpoint preserves monotonicity on both sides of the existing peak. Together with the singleton base case, this proves the equivalence.
Consequently, single-peakedness can be tested by reading a ranking from worst to best and repeatedly checking whether the next candidate is an endpoint of the remaining axis. With positions on the axis precomputed, this takes \(O(m)\) operations.
Let \(S_{\mathrm{bad}}=\{v\in S:\neg\operatorname{SP}(v,A)\}\). The minimum deletion mass is
\( \displaystyle R=\sum_{v\in S_{\mathrm{bad}}}\mu(v). \)
To prove the lower bound, take any feasible removal vector. For every \(v\in S_{\mathrm{bad}}\), feasibility requires \(\mu(v)-r_v=0\), hence \(r_v=\mu(v)\). Therefore its total removed mass is at least \(R\).
For attainment, remove exactly \(\mu(v)\) from every bad type and remove nothing from every other type. Every surviving type is single-peaked, so this removal vector is feasible and has total mass \(R\). If every type is bad, it removes all mass, as expressly permitted.
The single-peakedness tests take \(O(\tau m)\) operations. Exact summation is addressed in Section 6.
Fix a type \(v\). For \(1\le i\le j\le m\), let \(K_v(i,j)\) be the minimum adjacent-swap distance from the restriction of \(v\) to \(\{a_i,\ldots,a_j\}\) to any ranking single-peaked on that interval.
For a singleton, \(K_v(i,i)=0\). For \(i<j\), define
\( \displaystyle \ell_v(i,j)=\left|\{t:i<t\le j,\ \operatorname{pos}_v(a_i)<\operatorname{pos}_v(a_t)\}\right|, \)
\( \displaystyle r_v(i,j)=\left|\{t:i\le t<j,\ \operatorname{pos}_v(a_j)<\operatorname{pos}_v(a_t)\}\right|. \)
The recurrence is
\( \displaystyle K_v(i,j)=\min\bigl\{K_v(i+1,j)+\ell_v(i,j),\ K_v(i,j-1)+r_v(i,j)\bigr\}. \)
Proof of the recurrence. By Fact 2, the least-preferred candidate of any feasible target ranking is either \(a_i\) or \(a_j\).
If it is \(a_i\), all other candidates precede \(a_i\) in the target. The disagreeing pairs involving \(a_i\) are therefore exactly those counted by \(\ell_v(i,j)\). All remaining pair disagreements occur within \(\{a_{i+1},\ldots,a_j\}\), where the restricted target must be single-peaked. Thus every such target costs at least \(K_v(i+1,j)+\ell_v(i,j)\).
Conversely, append \(a_i\) as least preferred to an optimal target for that smaller interval. Fact 2 makes the resulting target single-peaked, and Fact 1 gives exactly that cost. The argument for \(a_j\) is identical. These two cases exhaust the feasible targets, proving the recurrence.
Compute states in increasing interval length. There are \(O(m^2)\) states, and computing each pair of counts directly takes \(O(m)\) operations. Hence each type takes \(O(m^3)\) operations.
The required output is exactly
\( \displaystyle D=\max_{v\in S}K_v(1,m). \)
Its computation takes \(O(\tau m^3)\) operations.
Fix a type \(v=(b_1,\ldots,b_m)\), listed from most to least preferred. Let \(h(x)\) be the position of \(x\) on the supplied axis \(A\). For \(2\le k\le m\), define
\( \displaystyle \alpha_k=\left|\{i<k:h(b_i)<h(b_k)\}\right|,\qquad \beta_k=\left|\{i<k:h(b_i)>h(b_k)\}\right|. \)
Then
\( \displaystyle \min_{B:\operatorname{SP}(v,B)}d(A,B)=\sum_{k=2}^{m}\min\{\alpha_k,\beta_k\}. \)
Proof. Fact 2 implies that all axes on which \(v\) is single-peaked can be generated as follows: start with \(b_1\), and for each \(k=2,\ldots,m\), insert \(b_k\) at either endpoint of the current axis.
For completeness, repeatedly removing the least-preferred candidate from any compatible axis removes endpoints; reversing these removals gives the stated construction. Conversely, every axis produced by this construction is compatible with \(v\), by the sufficiency direction of Fact 2.
If \(b_k\) is inserted at the left endpoint, it precedes every \(b_i\) with \(i<k\). Exactly \(\alpha_k\) of these pair orders disagree with \(A\). If it is inserted at the right endpoint, exactly \(\beta_k\) disagree.
Each unordered pair \(\{b_i,b_k\}\), with \(i<k\), is accounted for at step \(k\), and later endpoint insertions preserve its relative order. Moreover, the cost at step \(k\) depends only on which endpoint is chosen at that step, not on earlier choices. By Fact 1, the total distance is the sum of these step costs. Choosing a cheaper endpoint independently at every step proves both the lower bound and its attainment.
Therefore,
\( \displaystyle F=\max_{v\in S}\sum_{k=2}^{m}\min\{\alpha_k,\beta_k\}. \)
Computing the counts directly takes \(O(m^2)\) operations per type, so \(F\) takes \(O(\tau m^2)\) operations. The construction permits a different optimal axis for each type, exactly as required.
For each \(v\in S\), delete its top candidate from both \(v\) and \(A\), and apply the endpoint-elimination test from Fact 2.
Accept precisely when every restricted ranking passes. This is exactly the defining universal condition, and it takes \(O(\tau m)\) operations. Empty and singleton restrictions are accepted.
For \(m=1\), all four outputs therefore have their expected values: deletion mass, \(D\), and \(F\) are zero, and swoon-SP holds.
Write each input mass as \(p_v/q_v\), with positive integers encoded in binary. This also covers dyadic binary rationals.
To sum the bad masses, maintain an unreduced fraction \(N/Q\), initially \(0/1\). Adding \(p_v/q_v\) uses
\( \displaystyle N_{\mathrm{new}}=Nq_v+p_vQ,\qquad Q_{\mathrm{new}}=Qq_v. \)
At every stage, \(Q\) is a product of denominators from the input. Its bit length is therefore at most \(O(L)\). Since each partial sum is a sum of positive masses from a probability distribution, it lies in \([0,1]\); consequently \(0\le N\le Q\), and the numerator also has \(O(L)\) bits.
Schoolbook arithmetic thus sums the masses in \(O(\tau L^2)\) bit operations. If a reduced fraction is desired, Euclid’s algorithm gives a conservative additional bound of \(O(L^3)\) bit operations: there are \(O(L)\) divisions, each costing at most \(O(L^2)\).
The combinatorial algorithms use integers bounded by \(O(m^2)\), hence having \(O(\log(m+1))\) bits. After relabeling candidates by their axis positions, a conservative overall bound for all four outputs is
\( \displaystyle O\!\left(\tau m^3\log(m+1)+\tau L^2+L^3\right). \)
Only the listed \(\tau\) types are processed. No denominator-sized voter expansion occurs.
As an additional check, both swap formulas were compared with exhaustive minimization over all target rankings or axes for every input ranking with \(1\le m\le6\), covering \(873\) rankings. Every comparison agreed; the proofs above establish correctness for arbitrary \(m\).
⟨structured verdict parsed — rendered above⟩
The argument establishes exact polynomial-time computation of all four outputs. I found no mathematical errors or gaps requiring additional clarification.
Fact 1 correctly identifies adjacent-swap distance with the number of disagreeing unordered pairs. Each adjacent swap changes exactly one pair order, giving the lower bound; swapping adjacent descents decreases the inversion count by exactly one, giving attainment.
Fact 2 is correct in both directions. An internal least-preferred candidate necessarily has a less-preferred neighbor farther from the peak, a contradiction. Removing an endpoint preserves single-peakedness, and appending a least-preferred candidate at an endpoint preserves it. The singleton base case completes the recursive characterization.
\[
R=\sum_{v\in S_{\mathrm{bad}}}\mu(v)
\]
is correct. The argument handles both no bad types and all types being bad, including the permission to remove all mass.
The recurrence exhausts the possibilities because every feasible target places an interval endpoint last. When that endpoint is \(a_i\), the pairs whose orders change are exactly those in which \(v\) ranks \(a_i\) above another remaining candidate; these are precisely the pairs counted by \(\ell_v(i,j)\). The corresponding statement for \(a_j\) and \(r_v(i,j)\) is also correct.
Pairs involving the removed endpoint and pairs wholly inside the remaining interval are disjoint. Fact 1 therefore justifies adding their costs. Appending the endpoint to an optimal smaller target establishes attainment, so the recurrence proves equality rather than merely a bound.
The singleton initialization and increasing-interval-length evaluation are sufficient. There are \(O(m^2)\) states, each requiring \(O(m)\) operations with direct counting. Consequently, the stated \(O(\tau m^3)\) operation bound and
\[
D=\max_{v\in S}K_v(1,m)
\]
are correct.
The cost signs are correct. Inserting \(b_k\) on the left reverses exactly the supplied-axis pairs counted by \(\alpha_k\); inserting it on the right reverses exactly those counted by \(\beta_k\).
Each unordered pair is counted once, when its less-preferred member is inserted. Later insertions preserve that pair’s order. Crucially, either insertion places \(b_k\) before or after *all* previously inserted candidates, so its cost does not depend on earlier endpoint choices. The independent minimization is therefore justified:
\[
\min_{B:\operatorname{SP}(v,B)}d(A,B)
=\sum_{k=2}^{m}\min\{\alpha_k,\beta_k\}.
\]
Taking the maximum separately over support types respects the task’s allowance of a different axis for each type. Direct pair counting gives the claimed \(O(\tau m^2)\) operation bound.
Empty and singleton restrictions are explicitly accepted. For \(m=1\), the deletion mass and both distances are zero, and swoon-SP holds. Since the input is a probability distribution with positive support masses, the support is nonempty; both maxima are consequently defined.
Thus \(O(\tau L^2)\) bit operations for schoolbook summation is valid. The additional \(O(L^3)\) bound for optional fraction reduction is conservative and valid.
Swap counts and dynamic-programming values are bounded by the number of candidate pairs, so their bit lengths are \(O(\log(m+1))\). The combined bound
\[
O\!\left(\tau m^3\log(m+1)+\tau L^2+L^3\right)
\]
is a valid conservative polynomial bound under the explicit input representation. Routine input processing and relabeling are absorbed by this bound.
The reported number of exhaustive-test inputs is arithmetically correct: \(\sum_{m=1}^{6}m!=873\). No executable artifacts accompany the comparison claim, so I cannot independently authenticate those runs. They are supplementary and unnecessary for the correctness established by the proofs.
No repair is needed. The output resolves the requested complexity classification without expanding rational masses into repeated voters.
⟨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.