Answer: \(\mathrm{NP}\)-complete, even for \(\alpha=1\), \(d=k\), distinct approval types of weight two, and positive dyadic masses.
Theorem 10 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateMinimax Approval Voting with Out- liers is W[1]-hard, even when parameterized by s, d and k.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a finite support \(T\subseteq\{0,1\}^{m}\) of approval ballots with positive rational masses \(\mu_t\) summing to \(1\), integers \(k,d\), and a rational threshold \(\alpha\), does there exist a committee \(X\subseteq C\) with \(|X|=k\) such that \(\sum_{t\in T:\,d_H(\chi_X,t)\le d}\mu_t\ge\alpha\)?
Let \(C\) be a candidate set with \(|C|=m\ge1\). A society is given by its support: a nonempty list \(T\subseteq\{0,1\}^{m}\) of \(\tau\) distinct approval types, each with positive binary-rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The remaining inputs are integers \(1\le k\le m\), \(d\ge1\), and a binary rational \(0<\alpha\le1\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L,k,d\).
A feasible committee is a subset \(X\subseteq C\) with \(|X|=k\) satisfying \(\sum_{t\in T:\,d_H(\chi_X,t)\le d}\mu_t\ge\alpha\), where \(\chi_X\) is its characteristic vector and \(d_H\) is Hamming distance. The committee is indivisible; feasibility uses weak inequalities and requires no tie-breaking.
Is deciding whether a feasible committee exists in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For a finite list of voters, requiring at least \(s\) ballots within distance \(d\) of a size-\(k\) committee is \(\mathrm{W}[1]\)-hard parameterized by \(s+d+k\); a separate polynomial reduction from MAX-2-SAT establishes classical \(\mathrm{NP}\)-hardness. [Source](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p97.pdf)
No result settling exactly the normalized rational-mass problem above was located.
Result. The problem is \(\mathrm{NP}\)-complete, even when \(\alpha=1\), \(d=k\), every approval type approves exactly two candidates, and all masses are dyadic rationals.
1. Membership in \(\mathrm{NP}\).
A certificate is the characteristic vector \(\chi_X\in\{0,1\}^{m}\). Check that it has exactly \(k\) ones, and compute the set \(S=\{t\in T:d_H(\chi_X,t)\le d\}\).
The mass comparison can be performed exactly in polynomial time. Write the binary-encoded input rationals as \(\mu_t=p_t/q_t\) and \(\alpha=a/b\), with positive denominators. Define \(Q=b\prod_{t\in T}q_t\). Its bit length is \(O(L)\), because the sum of the input denominators’ bit lengths is at most \(L\). Feasibility is equivalent to the integer inequality
\(\sum_{t\in S}p_t(Q/q_t)\ge a(Q/b)\).
All integers involved have \(O(L)\) bits: each scaled mass is at most \(Q\), and their sum is at most \(Q\). Using elementary integer arithmetic, the denominator construction and scaled-weight computation take \(O(\tau L^2)\) bit operations.
Replace \(d\) by \(\min\{d,m\}\), which preserves every distance comparison. Computing the Hamming distances with binary counters takes \(O(m\tau\log(m+1))\) bit operations. Thus a sufficient verifier bound is
\(O(m\tau\log(m+1)+\tau L^2)\).
The certificate has \(m\le L\) bits, proving membership in \(\mathrm{NP}\).
2. Polynomial reduction from Vertex Cover.
We use the standard \(\mathrm{NP}\)-complete Vertex Cover problem: given a finite simple graph \(G=(V,E)\) and an integer \(b\), decide whether some \(Y\subseteq V\), with \(|Y|\le b\), meets every edge. This is Karp’s “Node Cover” problem. [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
We may restrict to \(E\ne\varnothing\) and \(1\le b\le |V|\). Instances outside these restrictions are immediately decidable and can be mapped to fixed restricted yes- or no-instances: a single edge with budget one, or a triangle with budget one, respectively. Consequently, this restriction preserves \(\mathrm{NP}\)-hardness.
Given a restricted instance, construct the society as follows:
Because the graph is simple, these types are distinct. Hence the support size is precisely \(\tau=|E|\ge1\).
For completeness, choose masses that satisfy even the restrictive interpretation of “binary rational” as a finite binary expansion. Enumerate the edges as \(e_1,\ldots,e_\tau\), and put \(r=\lceil\log_2\tau\rceil\) and \(D=2^r\). Assign \(\mu_{t_{e_i}}=1/D\) for \(i<\tau\), and \(\mu_{t_{e_\tau}}=(D-\tau+1)/D\).
Every mass is positive because \(D\ge\tau\), and their sum is
\((\tau-1)/D+(D-\tau+1)/D=1\).
This also covers \(\tau=1\), when the sole mass is one.
The output length is
\(O(m\tau+\tau\log(\tau+1)+\log(m+1))\),
so the construction is polynomial in the explicitly encoded graph’s input size. All target-input hypotheses hold, including \(1\le k\le m\) and \(d\ge1\).
3. Correctness of the reduction.
For any committee \(X\subseteq V\) with \(|X|=k\), and any edge \(e=\{u,v\}\), the symmetric-difference identity gives
\(d_H(\chi_X,t_e)=|X|+|e|-2|X\cap e|=k+2-2|X\cap e|\).
Since \(d=k\), we obtain
\(d_H(\chi_X,t_e)\le d\iff |X\cap e|\ge1\).
Thus an edge’s type is within the permitted distance exactly when the committee covers that edge.
Moreover, since all masses are positive and sum to one, meeting the threshold \(\alpha=1\) is equivalent to including every type in the distance calculation’s accepted set. Indeed, omitting any type reduces the accepted mass strictly below one. Therefore a size-\(k\) committee is feasible exactly when it is a vertex cover.
If the source instance has a vertex cover \(Y\) with \(|Y|\le b\), enlarge \(Y\) to a set \(X\) of exactly \(b\) vertices. This is possible because \(b\le |V|\), and adding vertices preserves the cover property. The resulting committee is feasible.
Conversely, a feasible committee has exactly \(b\) vertices and covers every edge, so it witnesses a yes-instance of Vertex Cover.
This proves both directions of the polynomial reduction and establishes \(\mathrm{NP}\)-hardness. Together with membership in \(\mathrm{NP}\), it proves the claimed \(\mathrm{NP}\)-completeness.
4. Explicit decision-time bound.
An exhaustive algorithm precomputes the scaled integer masses and examines all \(\binom{m}{k}\) committees. The preceding calculations give the bit-operation bound
\(O\!\left(\tau L^2+\binom{m}{k}\bigl(m\tau\log(m+1)+\tau L\bigr)\right)\).
Here \(k\) appears in the number of committees; \(d\) only affects the distance comparisons and can be capped at \(m\). In particular, fixed \(k\) permits polynomial-time enumeration, while the unrestricted problem is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The output resolves the task correctly. The reduction establishes \(\mathrm{NP}\)-hardness for the stated normalized rational-mass problem, and the certificate verifier establishes membership in \(\mathrm{NP}\). I found no major or minor mathematical issues.
The characteristic vector specifies an indivisible committee. Checking its number of ones enforces the exact cardinality requirement.
The common denominator \(Q=b\prod_{t\in T}q_t\) is positive and divisible by every input denominator. Consequently, multiplying the feasibility inequality by \(Q\) gives exactly the integer inequality stated in the output, without rounding or changing the weak inequality.
The bit-length estimate is correct: the logarithm of the denominator product is bounded by the sum of the input denominator bit lengths, hence by \(O(L)\). Normalization and positivity imply that each scaled mass and every partial sum of scaled masses are at most \(Q\). Also, \(\alpha\le1\) implies that the scaled threshold is at most \(Q\).
Elementary multiplication and division on these integers justify the stated \(O(\tau L^2)\) arithmetic bound. Computing all Hamming distances using binary counters fits within \(O(m\tau\log(m+1))\). Reading and capping the possibly large binary-encoded \(d\) is absorbed by the arithmetic bound.
Finally, the explicitly listed, nonempty support contains at least one vector of length \(m\), so \(m\le L\). The certificate therefore has polynomial length.
The cited theorem is the standard \(\mathrm{NP}\)-completeness of Vertex Cover on finite simple graphs, with an integer budget and the requirement that a cover have cardinality at most that budget. This matches the source problem as stated. [Karp’s original paper, reprinted with permission](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Restricting to a nonempty edge set and \(1\le b\le |V|\) is justified. Outside this range, the answer is immediately decidable. The proposed replacement instances satisfy the restrictions: a single edge with budget one is a yes-instance, and a triangle with budget one is a no-instance. Thus the restriction preserves hardness.
The construction satisfies every target-input condition:
For the masses, \(D\ge\tau\) gives \(D-\tau+1\ge1\), so all masses are strictly positive. Their displayed sum is exactly one. Their denominators are powers of two, so they are dyadic under the restrictive finite-binary-expansion interpretation as well.
The singleton-support case is handled correctly: \(\tau=1\) gives \(D=1\) and mass one. Each mass requires \(O(\log(\tau+1))\) bits, and each approval vector requires \(m\) bits. The stated output-length bound is therefore correct and polynomial for the explicitly encoded source graph. Writing the vectors and computing the masses also takes polynomial time.
The symmetric-difference identity is applied correctly. For a size-\(k\) committee and an edge, the distance is \(k+2-2|X\cap e|\).
With \(d=k\), the distance condition is equivalent to \(|X\cap e|\ge1\). This includes the boundary case of exactly one selected endpoint, where the distance equals \(k\) and acceptance follows from the required weak inequality.
Positivity and normalization make the threshold argument exact: accepting every type gives mass one, while omitting any type gives mass strictly below one. Thus feasibility is equivalent to covering every edge.
A source cover of size at most \(b\) can be enlarged to exactly \(b\) vertices because \(b\le |V|\). Adding vertices preserves coverage. Conversely, a feasible committee has exactly \(b\) vertices and, by the established equivalence, covers every edge.
These implications establish the required many-one reduction. Together with membership in \(\mathrm{NP}\), they prove the claimed restricted \(\mathrm{NP}\)-completeness.
The preprocessing bound agrees with the verifier analysis. For each committee, the distance calculations have the stated cost, and summing at most \(\tau\) scaled integers of \(O(L)\) bits costs \(O(\tau L)\). Committee-generation costs are absorbed by the displayed bound.
The dependence on \(k\) through \(\binom{m}{k}\), and on \(d\) through comparisons after capping it at \(m\), is correctly described. The fixed-\(k\) polynomial-time statement is valid and consistent with unrestricted \(\mathrm{NP}\)-completeness.
Actionable feedback: No mathematical repair or additional clarification 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.