Answer: \(\mathrm{NP}\)-complete
Corollary 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCC-SCORE, PLURALITY-CCAC, and PLURALITY-CCDC are NP-hard even for group-separable elections. Our NP-hardness proofs use caterpillar trees, which have the largest height possible. In the following sections we show algorithms for the case of trees with more moderate height.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a committee size \(k\), a rational distribution \(\mu\) over complete ranking types consistent with a group-separable clone decomposition tree \(G\), and a rational threshold \(\theta\), decide whether there is an integral committee \(W\subseteq C\) with \(|W|=k\) such that \(\sum_{\sigma}\mu_{\sigma}\min_{c\in W}(\operatorname{pos}_{\sigma}(c)-1)\le\theta\).
Let \(C\) be a candidate set with \(m\geq 1\), and let \(1\leq k\leq m\) be an integer.
A society is given by its support: a list of \(\tau\) distinct strict complete ranking types, each with positive mass \(\mu_\sigma\) encoded as a binary rational, with \(\sum_\sigma\mu_\sigma=1\). Here \(\tau\) is the support size, not the number of possible rankings.
The input includes an ordered rooted tree \(G\) whose leaves bijectively label \(C\), with at least two children per internal node. Each supported ranking is obtained by independently reversing child orders at internal nodes and reading the leaves from left to right.
Promise that \(G\) is a clone decomposition tree: a nonempty candidate set is consecutive in every supported ranking exactly when it is the leaf set of a subtree or the union of leaf sets of consecutive children of one internal node.
Given a binary rational threshold \(\theta\geq 0\), decide whether an integral committee \(W\subseteq C\), \(|W|=k\), satisfies \(\sum_\sigma\mu_\sigma\min_{c\in W}(\operatorname{pos}_\sigma(c)-1)\leq\theta\), where \(\operatorname{pos}_\sigma(c)\) is the rank of \(c\), starting at one. No committee tie-breaking is imposed.
Let \(L\) be the total input bit length; state running times in \(m,\tau,L,k\) and any additional parameters used.
Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite unweighted societies, Borda Chamberlin–Courant score decision is \(\mathrm{NP}\)-hard even with group-separable preferences, and admits an \(O(2^h)\operatorname{poly}(n,m,k)\)-time algorithm for clone-tree height \(h\) and voter count \(n\). [Verified source](https://www.ijcai.org/proceedings/2020/0029.pdf)
No result explicitly treating this normalized rational-mass formulation was located in the literature search.
The problem is \(\mathrm{NP}\)-complete on the promised inputs. Normalizing voter counts into rational masses preserves the decision question exactly. Supplying an exact clone decomposition tree also preserves hardness, because such a tree can be constructed in polynomial time.
I interpret the question existentially: does there exist a committee meeting the threshold? Evaluating a specified committee is polynomial-time solvable.
Rationals are understood to have binary-encoded numerators and denominators.
We use the stated finite-electorate hardness theorem: given an explicitly listed, group-separable profile with \(n\geq 1\) voters, committee size \(1\leq k\leq m\), and nonnegative integer threshold \(t\), deciding whether some committee \(W\) satisfies
\[ \sum_{v=1}^{n}\min_{c\in W}\bigl(\operatorname{pos}_{v}(c)-1\bigr)\leq t \]
is \(\mathrm{NP}\)-hard.
We also use the structural fact that every group-separable profile has an exact clone decomposition consisting entirely of \(Q\)-nodes, whose children can only be reversed. Both facts are stated in [Faliszewski, Karpov, and Obraztsova, Sections 3–4](https://www.ijcai.org/proceedings/2020/0029.pdf).
Below, we give an explicit polynomial construction of the required tree, using this structural existence result.
Let \(P\) be a nonempty group-separable profile, represented by its \(\tau\) distinct rankings. A common interval is a nonempty candidate set consecutive in every ranking. Let \(\mathcal I\) denote their family.
Two sets overlap if their intersection is nonempty and neither contains the other. A member of \(\mathcal I\) is strong if it overlaps no member of \(\mathcal I\).
Claim. In any exact decomposition tree containing only reversal nodes, the strong common intervals are precisely the leaf sets of its subtrees.
Proof. First consider a subtree leaf set \(S\). Every common interval is, by exactness, a subtree leaf set or a union of consecutive children at some node. Its generating node is an ancestor of, a descendant of, or incomparable with the node generating \(S\). Accordingly, that common interval contains \(S\), is contained in \(S\), or is disjoint from \(S\). Thus \(S\) is strong.
Conversely, suppose a common interval \(A\) is not a subtree leaf set. By exactness, it is the union of consecutive children indexed from \(a\) through \(b\) at some node with \(r\) children, where \(b-a+1\geq 2\) and this is a proper union.
If \(a>1\), the union of children indexed \(a-1\) and \(a\) is a common interval overlapping \(A\). If \(a=1\), properness gives \(b<r\), and the union of children indexed \(b\) and \(b+1\) overlaps \(A\). Hence \(A\) is not strong. This proves the claim.
To construct the tree, fix one supported ranking as reference and index its candidates in order. Every common interval is an interval in this reference ranking, so there are at most \(m(m+1)/2\) possibilities.
For each supported ranking \(\sigma\), a reference interval of cardinality \(s\) is consecutive in \(\sigma\) exactly when the maximum and minimum positions of its candidates differ by \(s-1\). Incrementally maintaining these extrema enumerates \(\mathcal I\) in \(O(\tau m^2)\) elementary operations.
Compare every pair of members of \(\mathcal I\) to identify the strong ones. This takes \(O(m^4)\) elementary operations. Strong intervals are laminar: two of them cannot overlap, by definition. Make each strong interval other than \(C\) a child of its smallest strict strong superset, and order siblings by their positions in the reference ranking.
The structural theorem guarantees an exact all-\(Q\) decomposition. By the claim, its subtree leaf sets are exactly the strong intervals just computed. Consequently, the constructed inclusion tree has the same hierarchy. At each node, the reference ranking orders its children either in the original order or its reversal. Choosing that order therefore preserves both the permitted rankings and the represented common intervals.
Thus the constructed tree satisfies both parts of the task’s promise. Every internal node has at least two children: singleton sets are strong, so maximal proper strong subsets cover their parent, and one proper subset alone cannot cover it.
With binary candidate indices, this construction takes
\[ O\!\left(L+(\tau m^2+m^4)\log(m+1)\right) \]
bit operations.
Take an instance of the finite problem from Section 2. Retain its candidate set and committee size. For every distinct ranking \(\sigma\), let \(r_\sigma\) be its multiplicity among the \(n\) voters. Output the mass
\[ \mu_\sigma=\frac{r_\sigma}{n} \]
and threshold
\[ \theta=\frac{t}{n}. \]
Every mass is positive, and their sum is one. Removing repeated copies of rankings does not change which candidate sets are consecutive in every ranking. Construct the exact tree from Section 3 and include it in the output.
For every committee \(W\), grouping identical rankings gives the identity
\[ \sum_\sigma\mu_\sigma \min_{c\in W}\bigl(\operatorname{pos}_\sigma(c)-1\bigr) = \frac{1}{n}\sum_{v=1}^{n} \min_{c\in W}\bigl(\operatorname{pos}_{v}(c)-1\bigr). \]
Because \(n>0\), the left-hand side is at most \(\theta=t/n\) exactly when the original dissatisfaction sum is at most \(t\). Committee cardinality is unchanged. This proves equivalence in both directions, without any tie-breaking assumption.
For the encoding bound, write \(S\) for the source input bit length. We have \(\tau\leq n\). Each mass requires \(O(\log(n+1))\) bits, and the threshold requires \(O(\log(t+1)+\log(n+1))\) bits. The output therefore has polynomial size in \(S\).
Sorting the explicit rankings and counting multiplicities takes polynomial time in \(S\); the tree construction takes \(O((\tau m^2+m^4)\log(m+1))\) bit operations after parsing. Hence the entire reduction is polynomial-time and always produces a promised instance. The target problem is therefore \(\mathrm{NP}\)-hard.
A certificate lists \(k\) distinct candidates. Constructing the position table costs \(O(L+\tau m\log(m+1))\) bit operations. Then each ranking’s dissatisfaction
\[ d_\sigma=\min_{c\in W}\bigl(\operatorname{pos}_\sigma(c)-1\bigr) \]
can be computed by inspecting the \(k\) committee members.
Write \(\mu_\sigma=p_\sigma/q_\sigma\) and \(\theta=a/b\), with positive denominators. Set \(Q=b\prod_\sigma q_\sigma\). The threshold comparison is equivalent to the integer comparison
\[ \sum_\sigma p_\sigma d_\sigma\frac{Q}{q_\sigma} \leq a\frac{Q}{b}. \]
The product \(Q\) has at most \(O(L)\) bits. Every integer used in this computation has \(O(B)\) bits, where
\[ B=L+\left\lceil\log_2(m+1)\right\rceil +\left\lceil\log_2(\tau+1)\right\rceil+2. \]
Using schoolbook integer arithmetic, certificate verification consequently takes
\[ O\!\left( L+\tau(m+k)\log(m+1)+(\tau+1)B^2 \right) \]
bit operations. Thus the problem belongs to \(\mathrm{NP}\) on its promised domain.
For completeness, exhaustive enumeration gives a deterministic decision algorithm taking
\[ O\!\left( L+\tau m\log(m+1) +\binom{m}{k} \left[\tau k\log(m+1)+(\tau+1)B^2\right] \right) \]
bit operations. It never expands rational masses into replicated voters.
Together with the reduction, this establishes \(\mathrm{NP}\)-completeness. In particular, a polynomial-time algorithm in the unrestricted input parameters would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output resolves the intended existential decision problem. The reduction preserves the objective exactly, the supplied tree satisfies the full promise, and exact rational arithmetic gives polynomial-time certificate verification. I found no mathematical gaps or incorrect complexity claims.
The prover explicitly interprets the question as asking whether there exists a committee \(W\) of size \(k\) meeting the threshold. This matches the intended complexity question. Its distinction between finding such a committee and evaluating a specified committee is correct.
The cited source supports both external results used:
Thus the source theorem concerns the same finite objective, and the structural theorem provides the required exact decomposition rather than merely a tree consistent with the rankings. [Faliszewski, Karpov, and Obraztsova](https://www.ijcai.org/proceedings/2020/0029.pdf)
The prover states the relevant results with sufficient precision and applies them to nonempty group-separable profiles, satisfying their hypotheses.
The claim identifying strong common intervals with subtree leaf sets is correct.
For a subtree leaf set \(S\), an interval represented by a consecutive union at an ancestor either includes the entire child branch containing \(S\), or excludes that branch. It therefore contains \(S\) or is disjoint from \(S\). Intervals generated below \(S\) are contained in \(S\), and intervals generated in incomparable branches are disjoint. Consequently, none overlaps \(S\).
For the converse, a common interval that is not a subtree must be a proper union of at least two consecutive children. The proposed adjacent two-child union overlaps it:
Both witnesses are common intervals by exactness. The exclusions of single-child unions and the full child union are justified because those are already subtree leaf sets.
The common-interval enumeration is valid. Every common interval occurs among the intervals of the reference ranking. For a set of \(s\) distinct candidates, the test
\[ \max_{c\in A}\operatorname{pos}_\sigma(c) - \min_{c\in A}\operatorname{pos}_\sigma(c) =s-1 \]
is necessary and sufficient for consecutiveness. Incremental extrema therefore support the stated \(O(\tau m^2)\) operation count.
Pairwise overlap testing among \(O(m^2)\) intervals supports the \(O(m^4)\) bound. Strong intervals are laminar, contain every singleton and \(C\), and consequently define the claimed inclusion tree.
The structural existence theorem and the proved characterization identify this hierarchy with that of an exact all-\(Q\) decomposition. Ordering children using a supported reference ranking changes each existing child order only by reversal. It therefore preserves both consistency of every supported ranking and the consecutive-child unions representing common intervals.
The argument excluding unary internal nodes is also valid: maximal proper strong subsets cover the parent because every candidate belongs to a singleton strong interval; one proper subset cannot provide that cover.
The stated bit bound accommodates parsing, position computations, interval comparisons, and tree construction. For \(m=1\), the construction yields a single labeled leaf, satisfying the internal-node condition vacuously.
Every output mass \(r_\sigma/n\) is positive, and the masses sum to one. Removing duplicate rankings preserves the common intervals and ranking consistency, since these depend on which rankings occur rather than their multiplicities.
The central identity is correct:
\[ \sum_\sigma \frac{r_\sigma}{n} \min_{c\in W}\bigl(\operatorname{pos}_\sigma(c)-1\bigr) = \frac{1}{n}\sum_{v=1}^{n} \min_{c\in W}\bigl(\operatorname{pos}_v(c)-1\bigr). \]
Since \(n>0\), comparison with \(t/n\) is equivalent in both directions to the original comparison with \(t\). Committee cardinality and the existential quantifier are preserved. No tie-breaking assumption enters the reduction.
The encoding bounds are correct. Explicit voter listing makes \(n\), \(\tau\), and \(m\) polynomially bounded by the source input size. The masses, threshold, rankings, and constructed tree therefore have polynomial total encoding length. The construction is polynomial-time and always produces a promised instance.
This establishes hardness for the target representation.
A size-\(k\) set of distinct candidates is a polynomial-size certificate. The position table and per-ranking minima can be computed within the stated bounds; checking candidate validity and distinctness is also covered.
With positive denominators,
\[ Q=b\prod_\sigma q_\sigma \]
is positive and divisible by every denominator. Multiplying the threshold inequality by \(Q\) therefore preserves its direction and gives exactly the displayed integer comparison.
The bit length of \(Q\) is \(O(L)\), because the sum of denominator encoding lengths is bounded by the total input length. Numerators, dissatisfaction values, products, and accumulated sums have \(O(B)\) bits for the stated \(B\). Schoolbook multiplication and division consequently justify
\[ O\!\left( L+\tau(m+k)\log(m+1)+(\tau+1)B^2 \right) \]
bit operations for verification.
This establishes membership in \(\mathrm{NP}\) on the promised domain. It does not require expanding rational masses into voters or checking the promise itself.
The exhaustive-search bound correctly combines one position-table construction with verification of all \(\binom{m}{k}\) committees. The boundary cases \(k=1\), \(k=m\), \(m=1\), and \(\theta=0\) introduce no undefined minima or failed comparisons.
The normalization reduction, exact-tree construction, and certificate verifier jointly establish the claimed completeness result. No additional lemma or clarification is needed to make the argument verifiable.
⟨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.