Answer: The decision problem is \(\mathrm{NP}\)-complete, even when all masses are dyadic.
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCONN-CC is NP-complete for SP profiles. This leads us to a more restricted domain, namely unani- mous profiles, in which every voter rank the same candidate on top, and strongly unanimous (SU) profiles, in which every voter has the same preference list. We have the following: 3It is a domain restriction, in which every voter is single-peaked wrt an axis π, i.e, for every voter v, and for each pair of candidates a, b, if either a π b π top(v) or top(v) π b π a holds, where top(v) is the first ranked candidate of voter v, then v ranks b above a.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a candidate graph \(H\), committee size \(k\), a common axis \(\pi\), a rational threshold \(q\), and a finite-support distribution \(\mu\) with binary-rational masses over rankings single-peaked on \(\pi\), is there a set \(S\subseteq C\) with \(|S|=k\), \(H[S]\) connected, and \(\sum_t \mu_t \max_{c\in S}(m-\operatorname{pos}_t(c))\ge q\)?
Input: a candidate set \(C\) with \(m\ge 1\), a simple undirected graph \(H\) on \(C\), an integer \(1\le k\le m\), a common linear axis \(\pi\), and a threshold \(q\in\mathbb{Q}\).
A society is given by its support: a list of \(\tau\) distinct strict rankings of \(C\), all single-peaked on \(\pi\), each with a positive binary-rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings.
Write \(\operatorname{pos}_t(c)\in\{1,\ldots,m\}\) for the position of \(c\) in ranking \(t\), with position \(1\) highest. A committee is a set \(S\subseteq C\) of exactly \(k\) candidates; its Borda–Chamberlin–Courant score is \(\sum_t\mu_t\max_{c\in S}(m-\operatorname{pos}_t(c))\).
Decide whether such a committee has \(H[S]\) connected and score at least \(q\). A singleton is connected. Let \(L\) be the total binary input length; state running times in \(m,\tau,L,k\).
Is this decision problem solvable in polynomial time in \(m,\tau,L,k\), or is it NP-hard?
For finite electorates with integer voter multiplicities, connected Borda–Chamberlin–Courant committee selection is NP-complete even for single-peaked profiles. Without the connectivity constraint, the discrete single-peaked problem is polynomial-time solvable.
No result for exactly the rational-mass formulation is established by the supplied material.
Proven conclusion. The problem is \(\mathrm{NP}\)-complete, using the finite-electorate hardness theorem supplied in the question. This holds even when every mass is dyadic, meaning that its denominator is a power of two. Consequently, a polynomial-time algorithm in \(m,\tau,L,k\) exists only if \(\mathrm{P}=\mathrm{NP}\).
Source problem. Use the supplied NP-completeness result for the same committee-selection problem with positive integer voter multiplicities. Merge identical rankings by adding their multiplicities. This preserves all committee scores and single-peakedness and takes polynomial time.
Write the resulting distinct rankings as \(1,\ldots,\tau\), their positive integer multiplicities as \(a_1,\ldots,a_\tau\), and their total multiplicity as \(A=\sum_{t=1}^{\tau}a_t\). For a committee \(S\), define
\(u_t(S)=\max_{c\in S}(m-\operatorname{pos}_t(c))\).
Its total finite-electorate score is
\(W(S)=\sum_{t=1}^{\tau}a_tu_t(S)\).
Each \(u_t(S)\) is an integer between \(0\) and \(m-1\), so \(W(S)\) is an integer. We may therefore take the source threshold to be an integer \(B\): replace a rational threshold by its ceiling. If the source uses average scores, first multiply its threshold by \(A\), then take the ceiling.
The reduction preserves \(C,H,k,\pi\) and all rankings. Thus committee feasibility, connectivity, and single-peakedness are preserved.
Construction of the masses. If arbitrary binary-encoded rational masses are allowed, simply use \(\mu_t=a_t/A\) and \(q=B/A\). This gives exact equivalence.
To cover the more restrictive interpretation requiring dyadic masses, choose a power of two \(D\) satisfying
\(8A\tau m\le D<16A\tau m\).
Set
\(b_t=\lfloor Da_t/A\rfloor\)
and
\(R=D-\sum_{t=1}^{\tau}b_t\).
Define
\(\mu_t=b_t/D\) for \(t<\tau\), and
\(\mu_\tau=(b_\tau+R)/D\).
These masses are dyadic and sum to one. They are positive because \(D\ge A\) and \(a_t\ge1\), giving \(b_t\ge1\). Set the target threshold to
\(q=(2B-1)/(2A)\).
Here is a uniform bound on the rounding error. Let
\(f_t=Da_t/A-b_t\), so \(0\le f_t<1\).
Since \(\sum_t Da_t/A=D\), we have \(R=\sum_t f_t\). Consequently,
\(\mu_t-a_t/A=-f_t/D\) for \(t<\tau\), while
\(\mu_\tau-a_\tau/A=\sum_{t<\tau}f_t/D\).
It follows that
\(\sum_t|\mu_t-a_t/A|=2\sum_{t<\tau}f_t/D\le2\tau/D\).
For every committee \(S\), its target score \(F(S)=\sum_t\mu_tu_t(S)\) therefore satisfies
\[
\]
\( |F(S)-W(S)/A|
\le (m-1)\sum_t|\mu_t-a_t/A|
\le 2\tau m/D
\le 1/(4A).\)
Correctness of the reduction. Suppose a feasible source committee satisfies \(W(S)\ge B\). The error bound gives
\(F(S)\ge B/A-1/(4A)>B/A-1/(2A)=q\).
Thus the same committee satisfies the target threshold.
Conversely, if a committee fails the source threshold, integrality gives \(W(S)\le B-1\). Hence
\(F(S)\le(B-1)/A+1/(4A)<B/A-1/(2A)=q\).
Such a committee fails the target threshold.
Connectivity and committee size are unchanged. Therefore the source instance is a yes-instance exactly when the constructed rational-mass instance is a yes-instance.
The construction has polynomial encoding length. If \(L_0\) is the source input length, then \(\log A=O(L_0)\), even when multiplicities are binary encoded. Also,
\(\log D=O(\log A+\log\tau+\log m)=O(L_0)\).
Every constructed numerator, denominator, and threshold consequently has \(O(L_0)\) bits. The target length is \(O(L_0^2)\), and ordinary integer arithmetic implements the construction in polynomial time; an \(O(L_0^3)\) bit-operation bound suffices. No expansion into \(A\) individual voters is needed. This proves NP-hardness.
Membership and running times. A certificate lists the \(k\) selected candidates. Check distinctness, size, and connectivity of \(H[S]\), treating a singleton as connected.
Precompute all positions in \(O(\tau m\log(m+1))\) bit operations. Each \(u_t(S)\) can then be computed by inspecting the \(k\) selected candidates, taking \(O(\tau k\log(m+1))\) bit operations altogether.
The score comparison can be exact. With ordinary binary numerator/denominator encodings, the product of all mass denominators has at most \(L\) bits. Express the score over this common denominator and compare it with \(q\) by cross multiplication. All integers involved have \(O(L)\) bits, and schoolbook arithmetic gives an \(O(\tau L^2)\) bound. Connectivity can be checked within \(O(m^2)\) time.
Thus certificate verification takes
\(O(m^2+\tau m\log(m+1)+\tau k\log(m+1)+\tau L^2)\)
bit operations, proving membership in \(\mathrm{NP}\).
For completeness, enumerating all committees gives an exact deterministic algorithm with running time
\(O(\tau m\log(m+1)+\binom{m}{k}(m^2+\tau k\log(m+1)+\tau L^2))\).
This is polynomial for each fixed \(k\), but the unrestricted problem is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The output correctly establishes \(\mathrm{NP}\)-completeness, including when all masses are dyadic. The reduction preserves the committee constraints, its rounding error is smaller than the source score gap, and its encoding length is polynomial. No substantive mathematical gaps were found.
The prover uses the finite-electorate hardness theorem explicitly supplied in USER_TASK. No additional hardness theorem is needed.
Merging identical rankings preserves their contribution to every committee’s score: their common utility is multiplied by the sum of their multiplicities. It also preserves single-peakedness and produces the distinct-ranking support required by the target formulation.
Because the multiplicities and utilities are integers, \(W(S)\) is an integer. Consequently, replacing a total-score threshold by its ceiling is valid. For an average-score threshold, multiplication by the positive total multiplicity \(A\), followed by taking the ceiling, is also valid.
The reduction leaves \(C,H,k,\pi\), and the rankings unchanged. Thus it preserves committee size, connectivity, and single-peakedness.
Assessment: Correct.
Taking \(\mu_t=a_t/A\) gives positive masses summing to one, and every committee has target score \(W(S)/A\). With \(q=B/A\), the two threshold conditions are equivalent.
This branch addresses the interpretation in which “binary-rational” means an arbitrary rational encoded in binary. The subsequent construction also covers the narrower dyadic interpretation.
Assessment: Correct.
The quantity \(8A\tau m\) is positive. A power of two exists in the stated interval
\(8A\tau m\le D<16A\tau m\), and its binary length has the claimed bound.
Since \(D\ge A\) and every \(a_t\ge1\), each \(b_t=\lfloor Da_t/A\rfloor\) is at least one. Flooring cannot increase the sum, so \(R\ge0\). Assigning \(R\) to the final numerator therefore preserves positivity.
The numerators sum to \(D\), making the masses sum to one. Their denominators are powers of two, as required. The rankings remain distinct because the construction changes only their masses.
The threshold \(q=(2B-1)/(2A)\) need not be dyadic, but USER_TASK permits any rational threshold.
Assessment: Correct.
The identities involving \(f_t\) and \(R\) are correct. For the first \(\tau-1\) rankings, the mass change is nonpositive; for the final ranking, it is the sum of the magnitudes of those changes. Hence the stated absolute-error identity holds:
\(\sum_t|\mu_t-a_t/A|=2\sum_{t<\tau}f_t/D\).
Since each utility lies between zero and \(m-1\), the triangle inequality gives the stated uniform score-error bound. Its final numerical step is valid because \(D\ge8A\tau m\), yielding
\(|F(S)-W(S)/A|\le1/(4A)\).
This calculation also covers \(\tau=1\), where the mass error is zero, and \(m=1\), where every utility is zero.
The isolated empty display before the bound is a harmless formatting artifact.
Assessment: Correct.
If \(W(S)\ge B\), the error bound places \(F(S)\) strictly above \(q\), with margin at least \(1/(4A)\).
If \(W(S)<B\), integrality gives \(W(S)\le B-1\). The error bound then places \(F(S)\) strictly below \(q\), again with margin at least \(1/(4A)\).
Thus the target’s non-strict acceptance condition introduces no equality ambiguity. These inequalities remain valid for negative or otherwise out-of-range thresholds.
Together with the unchanged feasibility constraints, this proves equivalence of the source and target instances.
Assessment: Correct.
The bounds on \(\log A\) and \(\log D\) are valid for binary-encoded multiplicities. Every constructed mass numerator is at most \(D\), and the threshold’s numerator and denominator have polynomial binary length.
There are at most polynomially many supported rankings relative to the source input length. Consequently, the stated \(O(L_0^2)\) target-length bound is valid, though not necessarily tight.
Using ordinary integer arithmetic, the claimed \(O(L_0^3)\) construction bound suffices. The construction never requires expanding binary multiplicities into individual voters.
Assessment: Correct.
A committee certificate has polynomial length. Its cardinality, distinctness, and induced connectivity can be checked in polynomial time, including the singleton convention.
The position and utility computations have the stated polynomial bounds. For exact score comparison, the product of the mass denominators has \(O(L)\) bits. Scaling the score to this denominator and cross-multiplying with the threshold uses integers of \(O(L)\) bits, including the additional utility factor.
The \(O(\tau L^2)\) arithmetic bound therefore suffices. Any ordinary graph-indexing overhead is also absorbed by the overall bound.
Assessment: Correct; membership in \(\mathrm{NP}\) is established.
The enumeration algorithm checks every committee of size \(k\). Its displayed running time correctly accounts for preprocessing and per-committee verification. For each fixed \(k\), the number of committees is polynomial in \(m\).
The polynomial reduction establishes \(\mathrm{NP}\)-hardness, and certificate verification establishes membership in \(\mathrm{NP}\). Therefore the claimed \(\mathrm{NP}\)-completeness and conditional exclusion of a general polynomial-time algorithm follow.
Required clarification or repair: None.
⟨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.