Answer: NP-complete
Theorem 3.3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateAssuming ETH, there is no 2o(d log d)poly(n, m)-time algorithm for Minimax Approval Voting.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(C\) with \(|C|=m\), a committee size \(k\), a distance bound \(d\), and a support \(\mathcal A\subseteq 2^C\) of \(\tau\) approval types with positive binary-rational masses \(\mu_A\) summing to \(1\), is there a committee \(K\subseteq C\), \(|K|=k\), such that \(\max_{A\in\mathcal A}|A\triangle K|\le d\)?
Given a candidate set \(C\) with \(|C|=m\ge 1\), integers \(0\le k\le m\) and \(d\ge 0\), a society is given by its support: a nonempty list \(\mathcal A\subseteq 2^C\) of \(\tau\) distinct approval types with positive binary-rational masses \(\mu_A\) summing to \(1\). Here \(\tau\) is the support size, not the number \(2^m\) of possible approval types; let \(L\) be the total input bit length.
A feasible committee is a set \(K\subseteq C\) with \(|K|=k\) and \(\max_{A\in\mathcal A}|A\triangle K|\le d\), where \(\triangle\) denotes symmetric difference. Empty approval sets are allowed. The bound applies to every supported type, without weighting its distance by its mass.
Is deciding whether a feasible committee exists polynomial-time solvable or NP-hard? State running times in \(m,\tau,L,k,d\).
For discrete Minimax Approval Voting, ETH excludes algorithms running in \(2^{o(d\log d)}\operatorname{poly}(n,m)\) time, where \(n\) is the number of votes ([source](https://arxiv.org/abs/1607.07906)). No separately stated complexity result for this distribution-support formulation was verified.
The decision problem is NP-complete, even when every supported approval type has exactly two candidates and \(d=k\).
It admits the following exact algorithms:
| Method | Running time |
|---|---|
| Enumerate size-\(k\) committees | \(O\!\left(L+\tau m\binom{m}{k}\right)\) |
| Search parameterized by \(d\) | \(O\!\left(L+\tau m(d+1)^{2d}\right)\), for \(d\ge 1\) |
Thus it is polynomial-time solvable for each fixed \(k\), and fixed-parameter tractable in \(d\). Under ETH, there is no algorithm with running time \(2^{o(d\log d)}\operatorname{poly}(m,\tau,L)\).
The explicit upper bounds count elementary operations on counters of \(O(\log(m+2))\) bits, together with input-reading cost \(O(L)\). Multiplying their arithmetic terms by \(O(\log(m+2))\) gives conservative bit-operation bounds.
For sets \(A,K\subseteq C\),
\( |A\triangle K|=|A|+|K|-2|A\cap K|. \)
Consequently, for a size-\(k\) committee, the constraint associated with \(A\) is precisely
\( |A\cap K|\ge \left\lceil\frac{|A|+k-d}{2}\right\rceil. \)
Neither expression involves \(\mu_A\). Because the distance bound applies to every supported type, changing its positive mass cannot change feasibility.
Any nonempty list of \(\tau\) distinct types can be equipped with positive dyadic masses of polynomial encoding length. Index the types by \(1,\ldots,\tau\), and put \(q=\lceil\log_2\tau\rceil\). Set
\( \mu_i=2^{-q}\quad(1\le i<\tau),\qquad \mu_\tau=\dfrac{2^q-\tau+1}{2^q}. \)
The final numerator is positive because \(2^q\ge\tau\), and the masses sum to one. Their total encoding length is \(O(\tau\log(\tau+1))\). For \(\tau=1\), this assigns mass one.
In particular, repeated identical votes in a discrete election can be discarded without changing feasibility. Conversely, a support instance becomes a discrete election by taking one vote of each supported type. Neither direction requires expanding rational masses into voter multiplicities.
A certificate is the committee \(K\), represented by its characteristic vector. Check its cardinality and compute its distance to every supported type. This takes \(O(L+\tau m)\) elementary operations. Therefore the problem belongs to NP.
Use the standard NP-complete Vertex Cover problem on simple graphs: given \(G=(V,E)\) and \(0\le b\le |V|\), decide whether there is a vertex cover of size at most \(b\). We may restrict to \(E\ne\varnothing\), since instances outside this restriction are trivial.
Construct the support instance as follows:
Because the graph is simple, these types are distinct. The support is nonempty, and \(\tau=|E|\). The construction has polynomial encoding length.
For any size-\(b\) committee \(K\) and edge \(e\),
\( |A_e\triangle K|=2+b-2|A_e\cap K|. \)
Hence
\( |A_e\triangle K|\le b \quad\Longleftrightarrow\quad |A_e\cap K|\ge 1. \)
Thus a feasible committee is exactly a vertex cover of size \(b\).
If the graph has a vertex cover of size at most \(b\), extend it to size exactly \(b\). This is possible because \(b\le |V|\), and adding vertices preserves the vertex-cover property. Conversely, any feasible committee is a vertex cover of size \(b\).
This proves both directions of the reduction, establishing NP-hardness and therefore NP-completeness.
There are \(\binom{m}{k}\) candidate committees. Checking each against all supported types gives running time
\( O\!\left(L+\tau m\binom{m}{k}\right). \)
In particular, for fixed \(k\), this is \(O(L+\tau m^{k+1})\).
Several boundary cases require only \(O(L+\tau m)\) time:
These cases include empty approval types.
We prove the bound \(O(L+\tau m(d+1)^{2d})\) directly. After handling the preceding cases, assume \(1\le d<m\).
Choose any supported type \(A_0\). Every size-\(k\) committee satisfies
\( |A_0\triangle K|\ge \bigl||A_0|-k\bigr|. \)
Therefore reject if \(\bigl||A_0|-k\bigr|>d\). Otherwise obtain a size-\(k\) committee \(K_0\) by deleting candidates from \(A_0\), or adding candidates to it, as necessary. Then
\( |K_0\triangle A_0|=\bigl||A_0|-k\bigr|\le d. \)
If a feasible committee \(K^\ast\) exists, the triangle inequality gives
\( |K_0\triangle K^\ast| \le |K_0\triangle A_0|+|A_0\triangle K^\ast| \le 2d. \)
The search starts at \(K_0\) with a budget of \(d\) swaps. At each node with committee \(K\):
All committees encountered have size \(k\).
Fix any feasible committee \(K^\ast\). At a node whose committee \(K\) violates the constraint for \(A\),
\( |A|+k-2|A\cap K^\ast| \le d <|A|+k-2|A\cap K|. \)
Thus \(|A\cap K^\ast|>|A\cap K|\). It follows that:
For the second statement, use equal committee sizes to obtain
\(|K^\ast\setminus A|=k-|K^\ast\cap A|<k-|K\cap A|=|S|\).
The chosen subsets retain these properties. If \(S_0=S\), it contains a candidate outside \(K^\ast\) by the preceding argument. Otherwise \(|S_0|=d+1\), whereas feasibility implies
\( |K^\ast\setminus A|\le |K^\ast\triangle A|\le d. \)
So again some \(x\in S_0\) lies outside \(K^\ast\).
Similarly, if \(T_0=T\), it contains a candidate belonging to \(K^\ast\). Otherwise \(|T_0|=d+1\), whereas
\( |A\setminus K^\ast|\le |A\triangle K^\ast|\le d. \)
Therefore some \(y\in T_0\) belongs to \(K^\ast\).
The search includes the branch swapping this \(x\) for this \(y\). On that branch,
\( \left|\bigl((K\setminus\{x\})\cup\{y\}\bigr)\triangle K^\ast\right| =|K\triangle K^\ast|-2. \)
Starting from distance at most \(2d\), successive such branches reach \(K^\ast\) within at most \(d\) swaps. The feasibility check is performed before checking whether the budget is exhausted, so that node is accepted.
Conversely, the algorithm accepts only after explicitly checking every constraint. This proves correctness.
Each node has at most \((d+1)^2\) children, and the depth is at most \(d\). For \(d\ge1\), the number of nodes is at most
\( \displaystyle\sum_{j=0}^{d}(d+1)^{2j} =O((d+1)^{2d}). \)
A node takes \(O(\tau m)\) elementary operations. The resulting bound is
\( O\!\left(L+\tau m(d+1)^{2d}\right) =2^{O(d\log(d+1))}\operatorname{poly}(m,\tau,L). \)
Theorem 3.3 of Cygan, Kowalik, Socała, and Sornat excludes a \(2^{o(d\log d)}\operatorname{poly}(n,m)\)-time algorithm for discrete Minimax Approval Voting under ETH. Their decision problem requires exactly \(k\) selected candidates and bounds the distance to every vote, matching the constraints here. [Source, Theorem 3.3](https://arxiv.org/pdf/1607.07906).
Given a discrete instance with \(n\ge1\) votes, remove duplicates and assign the dyadic masses from Section 1. This preserves \(m,k,d\) and feasibility, gives \(\tau\le n\), and takes polynomial time. After handling the trivial case \(d\ge m\), the constructed input length satisfies
\( L'=O\!\left(\tau m+\tau\log(\tau+1)+\log(m+1)\right) =\operatorname{poly}(n,m). \)
Therefore a support-instance algorithm running in
\(2^{o(d\log d)}\operatorname{poly}(m,\tau,L')\)
would solve discrete Minimax Approval Voting in
\(2^{o(d\log d)}\operatorname{poly}(n,m)\)
time, contradicting the cited theorem under ETH.
Thus the distribution-support formulation inherits the lower bound without needing a separately published complexity theorem.
⟨structured verdict parsed — rendered above⟩
The output proves the stated problem NP-complete. The reduction, exact algorithms, and transfer of the ETH lower bound are correct. No major or minor mathematical issues were found.
The polynomial-time claims concern fixed \(k\) and elementary boundary cases; they are consistent with NP-completeness for unrestricted inputs.
The identity
\[
|A\triangle K|=|A|+|K|-2|A\cap K|
\]
is correct. Substituting \(|K|=k\) and using that intersection cardinalities are integers gives exactly the stated ceiling inequality. This remains valid when its right-hand side is negative or exceeds the maximum possible intersection.
Since every supported type contributes a constraint regardless of its mass, the masses do not affect feasibility.
The proposed mass assignment is valid:
Consequently, both discarding duplicate discrete votes and replacing a support instance by one vote per supported type preserve feasibility. Neither operation requires expanding masses.
A characteristic vector specifies a committee using \(m\) bits. Its cardinality and all supported distances can be checked in \(O(L+\tau m)\) elementary operations.
These checks verify precisely the required certificate conditions. Empty approval sets cause no difficulty. Membership in NP follows.
The invoked source problem is stated precisely: Vertex Cover on simple graphs with a budget \(0\le b\le |V|\).
Restricting to graphs with at least one edge preserves NP-hardness because the excluded instances are trivially decidable. This restriction also ensures that the constructed support is nonempty and that \(m\ge1\).
The construction satisfies every input requirement:
For every edge \(e\) and size-\(b\) committee,
\[
|A_e\triangle K|=2+b-2|A_e\cap K|.
\]
Thus the distance constraint is equivalent to selecting at least one endpoint of the edge. The equivalence also holds when \(b=0\): neither problem admits a solution for a graph with an edge.
A cover of size at most \(b\) can be extended to size exactly \(b\), since \(b\le |V|\), and the extension remains a cover. Conversely, every feasible committee is a cover of size \(b\).
Both directions are established. The claimed restricted NP-completeness follows.
Enumerating all \(\binom{m}{k}\) committees and checking each against the support gives the claimed bound
\[
O\!\left(L+\tau m\binom{m}{k}\right).
\]
For fixed \(k\), the stated \(O(L+\tau m^{k+1})\) consequence is valid.
Each boundary characterization is correct:
These statements cover empty approval types and the relevant endpoint values of \(k\).
Rejecting when
\[
\bigl||A_0|-k\bigr|>d
\]
is necessary because cardinality difference is a lower bound on symmetric-difference distance.
Otherwise, the specified additions or deletions produce a valid size-\(k\) committee \(K_0\) at distance at most \(d\) from \(A_0\).
For any feasible \(K^\ast\), the triangle inequality gives
\[
|K_0\triangle K^\ast|\le2d.
\]
Since both committees have size \(k\), their symmetric difference consists of equally many deletions and additions. Thus the initial budget of \(d\) swaps is sufficient for the subsequent progress argument.
For a violated type \(A\), comparing its distances to \(K\) and feasible \(K^\ast\) correctly yields
\[
|A\cap K^\ast|>|A\cap K|.
\]
This implies both properties used in the proof:
The arbitrary truncations preserve these properties. When a chosen subset contains \(d+1\) elements, feasibility bounds the number of elements having the opposite membership property by \(d\). When no truncation occurs, the preceding existence argument applies directly.
Hence an enumerated pair always removes an element outside \(K^\ast\) and adds an element belonging to \(K^\ast\). Its swap reduces the symmetric-difference distance to \(K^\ast\) by exactly two.
Following such branches reaches an accepting committee within the available budget. Checking feasibility before budget exhaustion correctly handles acceptance at depth \(d\). Conversely, acceptance requires explicit verification of every constraint.
The search is therefore complete and sound.
There are at most \((d+1)^2\) children per node and at most \(d\) levels of swaps. For \(d\ge1\), the geometric sum is
\[
O((d+1)^{2d}).
\]
Constraint scans, subset selection, and committee handling fit within \(O(\tau m)\) per node. The stated overall bound follows:
\[
O\!\left(L+\tau m(d+1)^{2d}\right).
\]
The preceding handling of \(d=0\) and \(d\ge m\) justifies using counters of \(O(\log(m+2))\) bits during the nontrivial search. The stated conservative bit-operation conversion is consistent with these bounds.
The cited theorem was checked directly. [Theorem 3.3](https://arxiv.org/pdf/1607.07906) states the claimed ETH exclusion, and the paper’s decision definition requires exactly \(k\) selected candidates and distance at most \(d\) from every vote.
The proposed transformation preserves \(m,k,d\) and feasibility, while ensuring \(\tau\le n\). Its dyadic masses add only polynomial encoding length.
After the trivial \(d\ge m\) case is handled, the stated bound on \(L'\) includes sufficient space for the committee-size and distance parameters. Thus a support algorithm with the claimed forbidden running time would yield a discrete algorithm contradicting the cited theorem.
The transfer is valid; it does not require a separately published theorem for the support formulation.
No mathematical repair or additional clarification is required. The output resolves the assigned decision question and substantiates its running-time claims.
⟨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.