Answer: \(\mathrm{NP}\)-complete, even when every approval type has size two and every mass is a positive dyadic rational.
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor G being the independent property and ϕf ∈ {CCAV, PAV}, WD-(G, ϕf) is NP-hard, even if the associated graph is a path and every voter approves only two candidates.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a path \(G=(C,E)\), approval types \(A_1,\ldots,A_\tau\subseteq C\) with positive binary-rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\), and a rational threshold \(q\), does there exist an independent set \(W\subseteq C\) such that \(\sum_{i=1}^{\tau}\mu_i H_{|A_i\cap W|}\ge q\), where \(H_j=\sum_{h=1}^{j}1/h\) and \(H_0=0\)? This problem is NP-hard even when every \(A_i\) has size two.
Let \(G=(C,E)\) be a path with \(m=|C|\ge 1\). A society is given by its support: the list of \(\tau\) distinct nonempty approval types \(A_i\subseteq C\) with positive binary-rational masses \(\mu_i\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible approval types.
A feasible committee is any independent set \(W\subseteq C\), with no prescribed cardinality; the empty committee is allowed. Its score is \(\sum_{i=1}^{\tau}\mu_i H_{|A_i\cap W|}\), where \(H_0=0\) and \(H_j=\sum_{h=1}^{j}1/h\). Given \(q\in\mathbb{Q}\), decide whether some feasible committee has score at least \(q\). Let \(L\) be the total binary input length.
Is this decision problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard, even when every \(A_i\) has size two?
For a society represented as a finite multiset of approval ballots, PAV winner determination over independent committees is NP-hard even when the candidate graph is a path and every ballot approves exactly two candidates. No separate result for the rational-mass formulation is asserted here.
The problem is \(\mathrm{NP}\)-complete, even when every approval type has size two and every mass is a positive dyadic rational. Thus a running time polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The following reduction works directly with the support representation.
A certificate specifies a committee \(W\subseteq C\). We can check independence and compute all counts \(k_i=|A_i\cap W|\) in polynomial time.
Exact score comparison also takes polynomial time. Write \(\mu_i=a_i/b_i\), let \(B=m!\), and let \(P=\prod_i b_i\). Since every integer from \(1\) through \(m\) divides \(B\), each \(BH_{k_i}\) is an integer. Consequently, the score has the representation
\[ \operatorname{score}(W) =\frac{\sum_{i=1}^{\tau}a_i(P/b_i)(BH_{k_i})}{PB}. \]
The bit lengths of \(B\) and \(P\) are respectively \(O(m\log(m+1))\) and \(O(L)\). Computing this expression and comparing it with \(q\) by cross multiplication therefore takes polynomial time in \(m,\tau,L\). Under the usual explicit encoding of the candidate graph, this proves membership in \(\mathrm{NP}\).
We reduce from unweighted Max-Cut: given a simple undirected graph \(F=(V,D_F)\) and an integer \(K\), decide whether some cut has at least \(K\) crossing edges. This problem is \(\mathrm{NP}\)-complete, as established by [Garey, Johnson, and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1).
Write \(V=\{1,\ldots,n\}\) and \(e=|D_F|\). We may restrict to \(e\geq1\), since edgeless instances are decidable immediately.
For each vertex \(i\), introduce candidates \(t_i,f_i\). Introduce additional candidates \(z_1,\ldots,z_{n-1}\), and make the candidate graph the path in the following order:
\[ t_1,f_1,z_1,t_2,f_2,z_2,\ldots,z_{n-1},t_n,f_n. \]
Thus \(m=3n-1\). None of the approval types below contains any \(z_i\).
Let \(M\) be the smallest power of two strictly greater than \(2e\), and put \(r=M-2e\). In particular, \(r>0\) and \(M\leq4e\).
For every source edge \(\{i,j\}\in D_F\), introduce the two approval types
\[ \{t_i,t_j\},\qquad \{f_i,f_j\}, \]
each with mass \(1/M\). Introduce one further approval type \(\{t_1,f_1\}\), with mass \(r/M\).
All types have size two. They are distinct because \(F\) is simple, the \(t\)- and \(f\)-candidates are distinct, and the additional type contains both kinds of candidate. All masses are positive dyadic rationals, and their sum is
\[ \frac{2e+r}{M}=1. \]
The support size is exactly \(\tau=2e+1\).
Set the decision threshold to
\[ q=\frac{2r+3e+K}{2M}. \]
Call a committee *complete* if it contains exactly one of \(t_i,f_i\) for every \(i\), and contains no \(z_i\).
Let \(W\) be any independent committee. First remove all its \(z_i\). This preserves independence and leaves every approval intersection unchanged, so it preserves the score.
Because \(t_i\) and \(f_i\) are adjacent, the resulting committee contains at most one candidate from each pair. If it contains neither, add either one. After the separators have been removed, the only path edges between remaining candidates are the edges \(\{t_i,f_i\}\). These additions therefore preserve independence.
Each addition can only increase approval intersection sizes. Since \(H_{k+1}-H_k=1/(k+1)>0\) and all masses are positive, it cannot decrease the score.
It follows that every feasible committee can be transformed into a complete committee of at least the same score. Hence some feasible committee reaches \(q\) if and only if some complete committee reaches \(q\).
For a complete committee \(W\), define the source cut by
\[ S=\{i\in V:t_i\in W\}, \]
and let \(c(S)\) be its number of crossing edges.
Consider a source edge \(\{i,j\}\).
The additional type \(\{t_1,f_1\}\) has intersection size exactly one and contributes \(r/M\). Therefore
\[ \operatorname{score}(W) =\frac{r}{M}+\frac{3(e-c(S))}{2M}+\frac{2c(S)}{M} =\frac{2r+3e+c(S)}{2M}. \]
By the definition of \(q\), this score is at least \(q\) exactly when \(c(S)\geq K\).
Conversely, every source cut \(S\) defines a complete independent committee by selecting \(t_i\) for \(i\in S\) and \(f_i\) otherwise. The same score identity applies. Together with the completion argument, this proves both directions of the reduction.
The construction has \(m=3n-1\) candidates and \(\tau=2e+1\) distinct approval types. Since \(M\leq4e\), each mass requires \(O(\log(e+1))\) bits. The threshold requires \(O(\log(e+1)+\log(|K|+2))\) bits. The entire construction is therefore a polynomial-time many-one reduction.
This proves \(\mathrm{NP}\)-hardness for the stated support representation, including the stronger restriction to dyadic masses. Together with membership in \(\mathrm{NP}\), it settles the decision problem.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the support-based rational-mass problem. It establishes \(\mathrm{NP}\)-completeness even when every approval type has size two and every mass is a positive dyadic rational. No substantive gaps or required repairs were found.
The committee is a polynomial-size certificate under the explicitly stated graph encoding. Independence and approval-intersection counts are polynomial-time checks.
The exact arithmetic argument is valid: every denominator appearing in \(H_{k_i}\) divides \(B=m!\), and every mass denominator divides \(P=\prod_i b_i\). Thus the displayed score numerator is an integer and represents the score exactly. The stated bit-length bounds for \(B\) and \(P\) are correct. The numerator, intermediate products, and cross multiplication with the encoded rational threshold also have polynomial bit length. The case \(m=1\) is covered by \(1!=1\), and empty committees are covered by \(H_0=0\).
The cited theorem matches the source problem: unweighted Max-Cut decision on simple undirected graphs is \(\mathrm{NP}\)-complete. The cited paper establishes the required Simple Max Cut result. [Garey, Johnson, and Stockmeyer](https://www.acs.uwinnipeg.ca/ychen2/journalpapers/Garey-Johnson-2maxsat.pdf).
Restricting to \(e\geq1\) does not remove the hard instances; the excluded edgeless instances have an immediate answer. It also ensures \(n\geq2\), so the construction’s indexing is valid.
The candidate ordering defines a single path with \(2n+(n-1)=3n-1\) candidates. Each pair \(t_i,f_i\) is adjacent, while consecutive pairs are separated by a \(z_i\).
The numerical assertions are correct. The smallest power of two strictly exceeding \(2e\) satisfies \(2e<M\leq4e\), including when \(2e\) is itself a power of two. Consequently \(r=M-2e>0\).
All approval types contain exactly two distinct candidates. Simplicity of the source graph prevents repeated types within either family; the two families and the additional mixed type are mutually distinct. Hence \(\tau=2e+1\). The masses are positive dyadic rationals and sum exactly to one.
Removing separator candidates preserves independence and leaves the score unchanged because no approval type contains a separator.
Among the remaining candidates, the only path edges are the pair edges \(\{t_i,f_i\}\). Therefore adding one candidate from any unrepresented pair preserves independence. Harmonic scores are nondecreasing in each intersection count, so every such addition preserves or increases the total score.
This establishes the claimed transformation for every feasible committee, including the empty committee and committees initially containing separators. The threshold equivalence follows because complete committees are themselves feasible.
For a source edge whose endpoints are on the same side, the two intersection counts are two and zero, giving combined contribution \(3/(2M)\). For a crossing edge, they are one and one, giving contribution \(2/M\).
The additional approval type always has intersection count one in a complete committee and contributes \(r/M\). The resulting identity
\( \operatorname{score}(W)=(2r+3e+c(S))/(2M) \)
is correct.
Since \(2M>0\), comparison with the specified threshold is equivalent to \(c(S)\geq K\), with the inequality direction preserved. Every source cut produces the stated complete independent committee, and completion supplies the reverse implication for arbitrary target committees. Both directions are proved.
The candidate and support counts are polynomial in the explicit source-instance size. Candidate identifiers, the path, and the approval lists also require only polynomial space. The mass and threshold bit-length bounds are correct, and all construction steps use polynomial-time arithmetic.
The reduction directly outputs the required support representation; it does not rely on an unstated conversion from a ballot multiset. Together with membership in \(\mathrm{NP}\), it establishes the claimed classification. Isolated source vertices and arbitrary integer thresholds cause no failure in the construction or equivalence.
Actionable feedback: No mathematical clarification or repair is required.
⟨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.