Answer: \(\mathrm{NP}\)-complete
Theorem 6.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a profile R over a candidate set C and a positive integer k, it is NP-hard to decide if there exists a single-crossing profile R′ with c(R′) ≥k that can be obtained from R by decloning.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate set \(C\), a finite set \(T\) of complete ranking types over \(C\), a rational distribution \(\mu\) on \(T\), and an integer \(k\), does there exist a sequence of valid declonings whose pushforward distribution \(\delta_{\#}\mu\) is single-crossing—its positive-mass types admitting an order in which every pairwise preference is a prefix or suffix—and whose resulting candidate set \(C'\) satisfies \(|C'|\ge k\)?
Given a nonempty candidate set \(C\), let \(m=|C|\). A society is given by its support: a list \(T\) of \(\tau\) distinct strict complete ranking types, each with positive binary-rational mass \(\mu(t)\), with \(\sum_{t\in T}\mu(t)=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(k\ge1\) be a binary-encoded integer and \(L\) the total input bit length; state running times in \(m,\tau,L\), and \(k\).
At any stage, a clone set is a nonempty subset of the current candidates that forms a contiguous block in every positive-mass ranking. A valid decloning replaces such a block by one fresh candidate in every ranking; all other relative preferences remain unchanged. Any clone set is eligible, including the entire candidate set and sets that overlap other clone sets.
A finite sequence, possibly empty, induces a ranking map \(\delta\) and final candidate set \(C'\). Its pushforward is \((\delta_{\#}\mu)(r)=\sum_{t:\delta(t)=r}\mu(t)\), so coinciding output rankings have their masses added. Each move acts uniformly on all mass.
The output is single-crossing if its distinct positive-mass rankings admit a linear order in which, for every distinct \(a,b\in C'\), the rankings preferring \(a\) to \(b\) form a prefix or suffix, possibly empty or the whole order. This order is not supplied.
Is deciding whether some valid decloning sequence yields a single-crossing distribution with \(|C'|\ge k\) solvable in polynomial time, or is it \(\mathrm{NP}\)-hard?
For explicitly listed finite voters, this decision problem is \(\mathrm{NP}\)-complete; with the voter order fixed, it is polynomial-time solvable. [Verified results](https://home.agh.edu.pl/~faliszew/decloning.pdf).
No result addressing exactly the distribution-input problem above was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete. The hardness for explicitly listed voters transfers to the stated distribution model because clone eligibility and single-crossing feasibility depend only on the support, not on positive masses or ranking multiplicities.
The boundary cases are immediate: if \(k=1\), collapsing the entire candidate set gives a yes-instance; if \(k>m\), no decloning can leave sufficiently many candidates. The proof below settles the general problem.
For a finite list of rankings \(R\), let \(\operatorname{supp}(R)\) denote its set of distinct rankings.
Lemma 1. A candidate subset is a clone set for \(R\) if and only if it is a clone set for \(\operatorname{supp}(R)\). Moreover, \(R\) admits a single-crossing voter order if and only if its distinct rankings admit a single-crossing order.
Proof. Clone eligibility requires contiguity in every ranking. Repeating a ranking neither adds nor removes a contiguity constraint.
For single-crossingness, fix a candidate pair. Along an order of rankings, the pair’s comparison is a binary sequence. Its preferred side forms a prefix or suffix exactly when this sequence changes value at most once.
Suppose first that \(R\) has a single-crossing order. Retain one occurrence of each distinct ranking, preserving their order. A subsequence of a binary sequence with at most one change also has at most one change. The resulting order therefore witnesses single-crossingness of \(\operatorname{supp}(R)\).
Conversely, order the distinct rankings in a single-crossing order and replace each ranking by a consecutive group containing all its occurrences in \(R\). Repeating a binary value consecutively creates no additional changes. This gives a single-crossing order of all voters. \(\square\)
Lemma 2. For any ranking map \(\delta\) induced by valid decloning, the positive-mass support of the pushforward distribution is exactly \(\delta(T)\). Consequently, whether the output is single-crossing is independent of the particular positive masses on \(T\).
Proof. For every output ranking \(r\),
\( (\delta_{\#}\mu)(r)=\sum_{t\in T:\,\delta(t)=r}\mu(t). \)
Every summand is positive. Thus the sum is positive exactly when its indexing set is nonempty, which is equivalent to \(r\in\delta(T)\).
Move eligibility also depends only on the current support. Indeed, contiguity is required in every positive-mass ranking, and merging coincident rankings does not change that requirement. Inductively, changing the positive masses preserves every valid sequence and its output support. \(\square\)
In particular, output collisions cause no difficulty: merging their masses preserves precisely the set relevant to single-crossingness.
A partition \(\mathcal P=\{B_1,\ldots,B_q\}\) of \(C\) is a clone partition if every block \(B_i\) is contiguous in every original ranking. Its quotient ranking replaces each block by its label.
Lemma 3. Up to candidate renaming, the outputs obtainable by arbitrary finite valid decloning sequences are exactly the quotients by clone partitions of the original candidate set.
Proof. Track the original candidates represented by each current candidate.
Initially, each current candidate represents its singleton. Maintain the following invariant: these represented sets partition \(C\), each is contiguous in every original ranking, and each current ranking is obtained by replacing those original blocks by their current representatives.
Suppose a move contracts a current clone set \(D\). Its new representative corresponds to the union \(B\) of the original blocks represented by the members of \(D\). In every current ranking, the members of \(D\) occur consecutively. Expanding their represented blocks therefore shows that \(B\) occurs consecutively in the corresponding original ranking. The contraction preserves the invariant.
At termination, the represented sets consequently form a clone partition, and the output is its quotient.
Conversely, let \(\mathcal P\) be a clone partition. Contract its nonsingleton blocks in any order. A remaining block stays contiguous: contracting another, disjoint block removes no member of it and inserts no candidate between its members. Every contraction is therefore valid, and the resulting rankings are the quotient rankings. Singleton representatives can be renamed without affecting any comparison. \(\square\)
This argument includes the entire candidate set and arbitrary overlapping choices during a sequence. No restriction to a prescribed hierarchy of clone sets is needed.
We use the following supplied finite-profile theorem:
Given an explicitly listed profile of strict complete rankings and a positive threshold \(k\), deciding whether decloning can produce a single-crossing profile with at least \(k\) candidates is \(\mathrm{NP}\)-complete.
This is Theorem 6.4 of Elkind, Faliszewski, and Slinko. Their decloning operation replaces any clone block by a fresh candidate, including clone sets that are not supports of hierarchical subfamilies; their Definition 6.1 uses existence of a voter order with the same prefix-or-suffix condition as here. Thus the theorem’s hypotheses match the finite-profile version needed below. [Clone Structures in Voters’ Preferences, pp. 8, 11, and 27](https://home.agh.edu.pl/~faliszew/decloning.pdf)
Take a source instance with nonempty explicitly listed profile \(R=(R_1,\ldots,R_n)\), candidate set \(C\), and threshold \(k\). Remove duplicate rankings to obtain \(T=\{t_1,\ldots,t_\tau\}\), where \(\tau\le n\).
We assign positive dyadic masses, so the construction works even if “binary-rational” is interpreted as requiring a power-of-two denominator. Set
\(h=\lceil\log_2\tau\rceil,\qquad D=2^h.\)
Define
\(\mu(t_i)=1/D\quad\text{for }1\le i<\tau,\qquad \mu(t_\tau)=(D-\tau+1)/D.\)
Since \(D\ge\tau\), every mass is positive. Their sum is
\(\sum_{i=1}^{\tau}\mu(t_i)=((\tau-1)+(D-\tau+1))/D=1.\)
For \(\tau=1\), this simply assigns mass \(1\).
We retain the same candidate set and threshold \(k\).
Correctness. By Lemma 1, the original profile and its support have identical clone constraints. By Lemma 2, assigning positive masses does not change move eligibility at any stage. Hence a sequence is valid in the source instance exactly when it is valid in the constructed distribution instance.
For any such sequence, the finite output profile has distinct-ranking support \(\delta(T)\), and the distribution output has the same positive-mass support. Lemma 1 says that the finite output is single-crossing exactly when this support is single-crossing. Both outputs also have the same number of candidates. Therefore,
\((C,R,k)\text{ is a yes-instance}\quad\Longleftrightarrow\quad (C,T,\mu,k)\text{ is a yes-instance}.\)
Size and running time. Deduplication can be performed by lexicographically sorting the \(n\) length-\(m\) rankings, using \(O(nm\log(n+1))\) comparisons of candidate identifiers. Every constructed mass uses \(O(\log(\tau+1))\) bits. With candidates indexed by integers, the output length is
\(O\!\left(\tau m\log(m+1)+\tau\log(\tau+1)+\log(k+1)\right).\)
The construction is polynomial in the source input length and uses no iteration proportional to the numeric value of \(k\). It is therefore a polynomial-time many-one reduction, proving \(\mathrm{NP}\)-hardness.
A certificate consists of:
The quotient rankings in this second component may coincide.
The verifier performs the following checks.
Partition and eligibility. Check that every candidate belongs to exactly one nonempty block. For each input ranking, replace each candidate by its block label and check that every label appears in one contiguous run. This is exactly the condition that every partition block is a clone set.
Quotient construction. Replace each run by one occurrence of its label. Each resulting row is a strict complete ranking of the \(q\) blocks.
Single-crossing order. Check that the certificate lists every input type exactly once. For every distinct pair of block labels, scan their comparison along that order and reject if it changes more than once.
If these checks pass, Lemma 3 supplies a valid decloning sequence. By Lemma 1, deleting repeated quotient rankings preserves single-crossingness, and Lemma 2 identifies the remaining rankings with the output distribution’s support. Thus acceptance is sound.
Conversely, any successful sequence gives a clone partition by Lemma 3. Order its distinct output rankings in a single-crossing order, and place all input types yielding the same output ranking consecutively. This supplies a certificate that passes every check. Thus the verifier is complete.
The certificate has length
\(O\!\left(m\log(m+1)+\tau\log(\tau+1)\right).\)
After indexing candidates and constructing quotient positions, verification uses \(O(\tau m+\tau q^2)\) elementary operations. Including input reading, its running time is
\(O(L+\tau m^2)\)
on a word-RAM with \(O(\log(L+2))\)-bit index words; it is polynomial in the bit model as well. The threshold is handled by binary comparison, so dependence on \(k\) is through its encoding length, already included in \(L\).
The stated distribution-input problem is \(\mathrm{NP}\)-complete, even when all masses are positive dyadic rationals sharing a denominator at most \(2\tau\). The reduction handles both merged output rankings and unrestricted valid decloning sequences.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes \(\mathrm{NP}\)-completeness for the distribution-input problem in USER_TASK. I found no mathematical errors, unjustified theorem applications, or gaps requiring clarification.
For \(k=1\), the entire nonempty candidate set is an eligible clone set. Its contraction leaves one candidate, and single-crossingness is vacuous. For \(k>m\), no sequence can succeed because a contraction never increases the candidate count. This also covers \(m=1\).
Clone eligibility is a universal contiguity condition over rankings. Removing duplicate rankings preserves exactly these conditions.
For each candidate pair, the prefix-or-suffix condition is equivalent to its comparison sequence changing at most once. Both operations used in the proof preserve this property: taking a subsequence and replacing a value by consecutive copies.
The two directions establish the required existence statements about voter orders. In particular, the converse constructs an order of all voter occurrences; it does not assume their original order is fixed.
Positivity of every input mass is essential and is explicitly supplied by USER_TASK. Consequently, an output ranking has positive pushforward mass exactly when at least one input type maps to it. There is no cancellation or disappearance of an attained ranking.
The stage-by-stage eligibility argument is also valid: merging coincident rankings removes only redundant contiguity constraints. Changing the positive masses therefore preserves valid sequences and their output supports.
This proves the needed independence from masses throughout a sequence, rather than merely at its endpoint.
The invariant includes all three necessary facts: current representatives partition the original candidates, each represented block is contiguous in every original ranking, and current rankings are their quotients.
For a contraction, consecutive current representatives correspond to consecutive original blocks. Their union is therefore contiguous in each original ranking. This verifies the induction step even when current rankings have collided.
Conversely, the partition blocks are disjoint. Contracting one cannot insert an outsider into another or remove any of its members, so every remaining block stays eligible. The resulting quotient is therefore attainable.
Singleton contractions merely rename representatives and are covered by the qualification “up to candidate renaming.” Empty sequences correspond to the singleton partition. The proof imposes no hierarchy restriction on intermediate clone sets.
I checked the linked paper. The appendix formulation of Theorem 6.4 states the finite-profile decision problem as \(\mathrm{NP}\)-complete, although its main-text formulation states only \(\mathrm{NP}\)-hardness. Definition 6.1 uses existence of a voter order with the required pairwise separation condition. The decloning definition explicitly permits clone sets outside hierarchical subfamilies, and Definition 2.2 includes the entire candidate set. These match the hypotheses needed here. [Elkind, Faliszewski, and Slinko, pp. 2, 8, 11, and 27](https://home.agh.edu.pl/~faliszew/decloning.pdf)
Thus the reduction does not silently substitute a fixed-order or restricted-decloning problem.
Deduplication preserves initial clone constraints. Applying the support arguments at every subsequent stage preserves sequence validity in both directions. For any corresponding sequence, both outputs have the same candidate count and the same distinct-ranking support. Lemma 1 then gives exactly the claimed equivalence of yes-instances.
The mass calculation is correct. With \(h=\lceil\log_2\tau\rceil\) and \(D=2^h\), the final numerator \(D-\tau+1\) is positive, and all numerators sum to \(D\). For \(\tau=1\), the construction gives mass \(1\). For every \(\tau\ge1\), the denominator satisfies \(D\le2\tau\).
Each mass has encoding length \(O(\log(\tau+1))\). The stated output-length bound accounts for rankings, masses, and the binary threshold. The sorting bound counts identifier comparisons, as explicitly stated; their bit costs remain polynomial. There is no iteration proportional to the numerical value of \(k\).
The partition checks enforce precisely the original clone-partition condition. Collapsing its runs produces strict complete rankings of the blocks.
The second certificate component orders all input types, including types whose quotient rankings coincide. This is valid: accepting such an order gives a single-crossing order of the output support by deletion of duplicates.
Conversely, an attainable single-crossing output supplies a clone partition by Lemma 3. Grouping all input types with the same quotient ranking consecutively in a witnessing support order produces the required permutation certificate. Thus collisions do not compromise completeness.
For \(q=1\), the pairwise checks are vacuous, as required. For \(k>m\), no partition can satisfy the threshold.
The certificate-length bound covers one block label per candidate and a permutation of the input types. After quotient positions are constructed, each block pair can be checked in \(O(\tau)\) operations, giving \(O(\tau m+\tau q^2)\). Since \(q\le m\), including input reading yields the stated \(O(L+\tau m^2)\) word-RAM bound.
Index words of \(O(\log(L+2))\) bits suffice for the explicitly represented candidates, ranking types, and positions. Binary comparison handles the threshold without numerical dependence on \(k\). The bit-model claim is polynomial and does not assert the same exact operation bound.
No repair or additional clarification is needed. The support reduction establishes hardness, and the partition certificate establishes membership in \(\mathrm{NP}\).
⟨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.