Answer: NP-complete, even when the supplied tree has diameter \(4\) and pathwidth \(2\).
Theorem 4.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a profile P that is single-peaked on a tree, a target committee size k, and a target score B, it is NP-complete to decide whether there exists a committee of size k with score at least B under the utilitarian Chamberlin–Courant rule with the Borda scoring function. Hardness holds even restricted to profiles single-peaked on a tree with diameter 4 and pathwidth 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a tree \(T\) on \(C\), a finite-support rational distribution \(\mu=(\mu_t)\) over complete ranking types \(\pi_t\) that are all single-peaked on \(T\), a committee size \(k\), and a rational threshold \(b\), decide whether there exists an integral committee \(W\subseteq C\) with \(|W|=k\) such that \(\sum_t \mu_t\bigl[-(\operatorname{pos}_{\pi_t}(\operatorname{top}_{\pi_t}(W))-1)\bigr]\ge b\).
A society is given by its support: a list of \(\tau\) distinct strict complete ranking types \(\pi_t\) over a candidate set \(C\), each with positive mass \(\mu_t\) encoded as a binary rational, with \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings.
Let \(m=|C|\ge1\). A tree \(T\) on \(C\) is supplied; each ranking is single-peaked on \(T\), meaning that every nonempty initial segment of the ranking induces a connected subtree.
The remaining inputs are an integer \(1\le k\le m\) and a binary rational threshold \(b\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L,k\).
For a nonempty committee \(W\subseteq C\), let \(\operatorname{top}_{\pi_t}(W)\) be its highest-ranked member, with ranking positions numbered from \(1\). Its utilitarian Chamberlin–Courant score is \(S(W)=\sum_{t=1}^{\tau}\mu_t[-(\operatorname{pos}_{\pi_t}(\operatorname{top}_{\pi_t}(W))-1)]\). Committee membership is integral; members need not represent positive mass, and there are no representation quotas.
Is deciding whether some \(W\subseteq C\) satisfies \(|W|=k\) and \(S(W)\ge b\) solvable in polynomial time, or is it NP-hard?
For finite electorates with unit-weight voters, this Borda utilitarian Chamberlin–Courant decision problem is NP-complete, even when the supplied tree has diameter \(4\) and pathwidth \(2\).
For finite electorates whose rankings are single-peaked on a star, Borda utilitarian Chamberlin–Courant winner determination is polynomial-time solvable.
The decision problem is NP-complete, even when the supplied tree has diameter \(4\) and pathwidth \(2\). The stated finite-electorate hardness transfers by grouping identical rankings and normalizing their multiplicities. Binary rational masses make this conversion polynomial in size.
Here \(k\) is part of the input. The boundary case \(k=m\) is immediate: the only committee has score \(0\), so the answer is yes exactly when \(b\le 0\).
Use the finite-electorate NP-completeness result given in the question. Consider a source instance with \(n\ge 1\) explicitly listed unit-weight voters, candidate set \(C\), supplied tree \(T\), committee size \(k\), and threshold \(B\). Write its usual Borda utilitarian score as
\[ U(W)=\sum_{i=1}^{n}\bigl(m-\operatorname{pos}_{\pi_i}(\operatorname{top}_{\pi_i}(W))\bigr). \]
The source question is whether some committee of size exactly \(k\) satisfies \(U(W)\ge B\).
Group identical rankings. Let the resulting distinct types be \(\pi_1,\ldots,\pi_\tau\), with positive integer multiplicities \(n_1,\ldots,n_\tau\). Thus
\[ \sum_{t=1}^{\tau}n_t=n, \qquad \tau\le n. \]
Construct the target society by setting
\[ \mu_t=\frac{n_t}{n}, \qquad b=\frac{B-n(m-1)}{n}. \]
Keep \(C,T,k\) unchanged. Every mass is positive, and their sum is \(1\). Every retained ranking already occurred in the source electorate, so it remains single-peaked on the supplied tree.
For every nonempty committee \(W\),
\[ \begin{aligned} nS(W) &=\sum_{t=1}^{\tau}n_t \bigl(1-\operatorname{pos}_{\pi_t}(\operatorname{top}_{\pi_t}(W))\bigr)\\ &=U(W)-n(m-1). \end{aligned} \]
Consequently,
\[ U(W)\ge B \quad\Longleftrightarrow\quad S(W)\ge b. \]
The feasible committees are unchanged: both instances require exactly \(k\) integral members and impose no representation quotas.
If the source theorem instead uses the negative rank-offset convention directly, the same construction uses its source threshold divided by \(n\).
Each fraction \(n_t/n\) needs \(O(\log(n+1))\) bits. The new threshold has bit length
\[ O\bigl(\operatorname{bits}(B)+\log(n+1)+\log(m+1)\bigr). \]
After indexing candidates by integers, the target input length satisfies
\[ L=O\bigl( \tau m\log(m+1) +\tau\log(n+1) +m\log(m+1) +\operatorname{bits}(B) +\log(n+1) \bigr). \]
Because the source electorate is explicitly listed and \(\tau\le n\), this is polynomial in the source input length. Grouping rankings can be performed by sorting their explicit lists, also in polynomial time.
The reduction leaves the tree unchanged. Hence the supplied source hardness for trees of diameter \(4\) and pathwidth \(2\) holds for the target problem under those same restrictions.
This proves NP-hardness. The stated polynomial-time result for finite electorates on stars concerns a narrower tree class and does not contradict this reduction.
A certificate lists \(k\) distinct candidates, requiring \(O(k\log(m+1))\) bits. Check membership in \(C\), distinctness, and cardinality exactly \(k\).
For each ranking type, determine
\[ r_t=\min_{c\in W}\operatorname{pos}_{\pi_t}(c), \qquad d_t=r_t-1. \]
Then the required comparison is
\[ -\sum_{t=1}^{\tau}\mu_t d_t\ge b. \]
This comparison can be performed exactly. Write the encoded rationals as
\[ \mu_t=\frac{p_t}{q_t}, \qquad b=\frac{a}{q_b}, \]
with positive denominators, and set
\[ D=q_b\prod_{t=1}^{\tau}q_t. \]
Since \(D>0\), the comparison is equivalent to the integer inequality
\[ -\sum_{t=1}^{\tau}p_t d_t\frac{D}{q_t} \ge a\frac{D}{q_b}. \]
The bit length of \(D\) is at most the sum of the encoded denominator lengths, hence \(O(L)\). All intermediate integers have \(O(L)\) bits: the additional factors and summation contribute only \(O(\log(m+1)+\log(\tau+1))\) bits, which are already \(O(L)\).
Using straightforward ranking scans and schoolbook integer arithmetic gives the conservative verification bound
\[ O\bigl((\tau m+k)L+(\tau+1)L^2\bigr) \]
bit operations. This is polynomial in \(m,\tau,L,k\), so the problem belongs to NP.
Together with the reduction, this establishes NP-completeness.
⟨structured verdict parsed — rendered above⟩
The prover’s conclusion is correct: the target problem is NP-complete, including under the stated restrictions on the supplied tree. The reduction and NP-membership argument are rigorous. No mathematical gaps were found.
USER_TASK. Its source instances have explicitly listed unit-weight voters, the same ranking domain, and the same committee objective up to a constant score shift. Using this supplied result requires no additional theorem.\[
nS(W)=U(W)-n(m-1).
\]
Since \(n>0\), setting \(b=(B-n(m-1))/n\) gives the claimed equivalence in both directions. Committee size and all feasibility conditions are preserved.
\[
O\bigl((\tau m+k)L+(\tau+1)L^2\bigr).
\]
This establishes polynomial-time certificate verification without expanding rational masses into voters.
No additional clarification or repair 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.