Answer: For every fixed \(p\ge3\), the problem is \(\mathrm{NP}\)-complete and \(\mathrm{W[1]}\)-hard parameterized by \(K\); it is not \(\mathrm{FPT}\) unless \(\mathrm{FPT}=\mathrm{W[1]}\).
Theorem 1, part (1) — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor each constant p greater than 2, the MaxCover problem with frequencies upper-bounded by p is W[1]-complete (when parameterized by the number of sets in the solution). (2) For each constant p, p ≥1, MaxCover where each element belongs to at least p sets is W[2]-hard and belongs to W[P] (when parameterized by the number of sets in the solution) For parameter T, the number of elements that we should cover, Bl¨aser gave an FPT algorithm (2003) for MaxCover.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For fixed \(p\ge 3\), an instance gives a candidate set \(C\), a committee bound \(K\), a finite support \(\mathcal A\) of approval types \(A\subseteq C\) with \(|A|\le p\), binary-rational masses \(\mu_A>0\) summing to \(1\), and a rational threshold \(q\). Is there a committee \(W\subseteq C\), \(|W|\le K\), such that \(\sum_{A:A\cap W\ne\varnothing}\mu_A\ge q\)?
Fix an integer \(p\ge 3\). An instance gives a candidate set \(C\), with \(m=|C|\), a nonnegative integer committee bound \(K\), and a threshold \(q\in\mathbb Q\).
A society is given by its support: a list \(\mathcal A\) of distinct approval types \(A\subseteq C\), each satisfying \(|A|\le p\), with positive binary-rational masses \(\mu_A\) summing to \(1\). Empty approval types are allowed.
Here \(\tau=|\mathcal A|\) is the support size, not the number of possible approval types; \(L\) is the total input bit length.
A committee is a subset \(W\subseteq C\) with \(|W|\le K\). Its represented mass is \(\sum_{A\in\mathcal A:A\cap W\ne\varnothing}\mu_A\). The decision problem asks whether some committee has represented mass at least \(q\).
Is this decision problem in \(\mathrm P\) or \(\mathrm{NP}\)-hard for each fixed \(p\ge3\)? If it is \(\mathrm{NP}\)-hard, is it nevertheless \(\mathrm{FPT}\) parameterized by \(K\)? State running times in \(m,\tau,L,K\).
Discrete MaxCover with frequencies bounded by fixed \(p\ge3\) is \(\mathrm{W[1]}\)-complete parameterized by \(K\), and is \(\mathrm{NP}\)-complete even with frequency bound \(2\). [Verified source](https://arxiv.org/html/1309.4405).
No result settling the exact normalized rational-mass formulation was verified in the literature search.
For every fixed \(p\ge 3\), the decision problem is \(\mathrm{NP}\)-complete and is \(\mathrm{W[1]}\)-hard parameterized by \(K\). Consequently, it has no exact algorithm running in \(f(K)\operatorname{poly}(m,\tau,L)\) time unless \(\mathrm{FPT}=\mathrm{W[1]}\).
The hardness reduction below uses only dyadic masses, so it applies whether “binary-rational” means dyadic rationals or arbitrary rationals encoded in binary.
Write each mass as \(\mu_A=a_A/b_A\), with positive integer denominator, and write \(q=u/v\), with \(v>0\). Define the common denominator
\(D_0=v\prod_{A\in\mathcal A}b_A.\)
Set \(w_A=a_A(D_0/b_A)\) and \(Q=u(D_0/v)\). For every committee \(W\),
\(\displaystyle \sum_{A:A\cap W\ne\varnothing}\mu_A\ge q \quad\Longleftrightarrow\quad \sum_{A:A\cap W\ne\varnothing}w_A\ge Q.\)
The bit length of \(D_0\) is at most the sum of the input denominator bit lengths, hence is \(O(L)\). The integers \(w_A\) and \(Q\) also have \(O(L)\) bits. Schoolbook multiplication and division therefore construct these integers in \(O((\tau+1)L^2)\) bit operations.
A certificate lists at most \(\min(K,m)\) candidates. Check its validity and scan every approval type to determine whether it intersects the committee. Each type contains at most \(p\) candidates, and the subsequent integer additions and comparison are polynomial in \(L\). A conservative bound for verification, including preprocessing, is
\(O((m+p\tau+1)L^2).\)
Thus the problem belongs to \(\mathrm{NP}\).
Consider an explicit discrete MaxCover instance with universe \(U\), sets \(S_1,\ldots,S_m\), committee bound \(K\), and integer target \(t\). Each element belongs to at most \(p\) sets.
The supplied source establishes \(\mathrm{NP}\)-completeness even for frequency bound \(2\), and \(\mathrm{W[1]}\)-completeness for every fixed frequency bound \(p\ge3\), parameterized by \(K\). These are the source problems used here. [Skowron–Faliszewski, Sections 3–4](https://arxiv.org/html/1309.4405).
First handle trivial source instances. If \(t\le0\), output a fixed yes-instance; if \(t>|U|\), output a fixed no-instance. Both can use the same bound \(K\), the empty candidate set, and the sole approval type \(\varnothing\) of mass \(1\), with thresholds \(0\) and \(1\), respectively.
It remains to consider \(n=|U|\ge1\) and \(1\le t\le n\).
Let \(C=\{1,\ldots,m\}\). For each element \(e\in U\), define its approval type by
\(A_e=\{i:e\in S_i\}.\)
The frequency hypothesis gives \(|A_e|\le p\), including the possibility \(A_e=\varnothing\).
For each occurring type \(A\), let
\(c_A=|\{e\in U:A_e=A\}|.\)
Take \(c_A=0\) for absent types. Choose the power of two
\(D=2^{\lceil\log_2 n\rceil}.\)
For every nonempty type with \(c_A>0\), assign mass
\(\mu_A=c_A/D.\)
Assign the empty type mass
\(\mu_\varnothing=(c_\varnothing+D-n)/D,\)
and include it in the support precisely when this quantity is positive. Finally, retain the committee bound \(K\) and set \(q=t/D\).
Every listed mass is positive and dyadic. Approval types are distinct because equal types were grouped. Their sizes remain at most \(p\).
The masses sum to \(1\), since
\(\displaystyle \sum_{A\ne\varnothing}\mu_A+\mu_\varnothing =\frac{n-c_\varnothing+c_\varnothing+D-n}{D}=1,\)
where a zero empty-type mass contributes nothing and is omitted.
There are at most \(n+1\) support types. Since \(n\le D<2n\), every mass and the threshold have \(O(\log(n+1))\) bits. With candidates indexed in binary, the output length is bounded by
\(O\!\left( m\log(m+1) +(n+1)\bigl(p\log(m+1)+\log(n+1)\bigr) +\log(K+1) \right).\)
Grouping types and producing this output takes polynomial time in the explicit source input length. No multiplicity is expanded.
Let \(W\subseteq C\). An element \(e\) is covered by the selected source sets exactly when
\(e\in\bigcup_{i\in W}S_i \quad\Longleftrightarrow\quad A_e\cap W\ne\varnothing.\)
The empty approval type is never represented. Therefore,
\(\displaystyle \sum_{A:A\cap W\ne\varnothing}\mu_A =\frac{\left|\bigcup_{i\in W}S_i\right|}{D}.\)
Consequently,
\(\displaystyle \sum_{A:A\cap W\ne\varnothing}\mu_A\ge q \quad\Longleftrightarrow\quad \left|\bigcup_{i\in W}S_i\right|\ge t.\)
The two instances have identical answers, and their committee bounds are identical.
For classical complexity, apply the reduction to the frequency-\(2\) MaxCover problem. Its output types have size at most \(2\), so they satisfy every fixed bound \(p\ge3\). This proves \(\mathrm{NP}\)-hardness. Together with Section 1, it proves \(\mathrm{NP}\)-completeness.
For parameterized complexity, fix \(p\ge3\) and apply the reduction to the supplied \(\mathrm{W[1]}\)-complete frequency-\(p\) MaxCover problem. The reduction is polynomial and preserves \(K\), hence is a parameterized reduction. Our problem is therefore \(\mathrm{W[1]}\)-hard.
If an exact algorithm ran in \(f(K)\operatorname{poly}(m,\tau,L)\) time, composing it with this reduction would give an \(\mathrm{FPT}\) algorithm for that \(\mathrm{W[1]}\)-complete source problem. This would imply \(\mathrm{FPT}=\mathrm{W[1]}\).
This argument establishes hardness for the rational-mass formulation; it does not assert its membership in \(\mathrm{W[1]}\).
An explicit exhaustive algorithm gives an \(\mathrm{XP}\) upper bound.
Let
\(R=\bigcup_{A\in\mathcal A}A,\qquad r=|R|\le\min(m,p\tau),\qquad k=\min(K,r).\)
Candidates outside \(R\) represent no mass and can be removed from a committee. Representation is monotone under adding candidates: every represented type remains represented. Thus every committee contained in \(R\) of size at most \(k\) can be extended to one of size exactly \(k\) without decreasing its represented mass.
It therefore suffices to enumerate the \(\binom{r}{k}\) subsets of \(R\) of size \(k\) and verify each exactly. Using Section 1, a conservative bit-operation bound is
\(O\!\left( (m+p\tau+1)L^2 +\binom{r}{k}(r+p\tau+1)L^2 \right).\)
In particular, this is bounded by
\(O\!\left( (\min(m,p\tau)+1)^K(m+p\tau+1)L^2 \right).\)
The exponent depending on \(K\) makes this an \(\mathrm{XP}\) bound, rather than an \(\mathrm{FPT}\) bound.
The boundary cases are polynomial: thresholds \(q\le0\) are always attainable; thresholds \(q>1\) are impossible; \(K=0\) permits represented mass \(0\); and \(K\ge r\) permits the maximum mass \(1-\mu_\varnothing\), taking \(\mu_\varnothing=0\) when absent.
⟨structured verdict parsed — rendered above⟩
The output resolves the task correctly. The normalization reduction preserves both the decision answer and the parameter \(K\), including when masses must be dyadic. The arithmetic and exhaustive-search bounds are valid. I found no major or minor issues requiring repair.
The common denominator \(D_0=v\prod_{A\in\mathcal A}b_A\) is a positive integer divisible by every mass denominator and by the threshold denominator. Thus the quantities \(w_A\) and \(Q\) are integers, and multiplying the decision inequality by \(D_0\) preserves its direction. This remains valid for negative thresholds.
The product denominator has \(O(L)\) bits because the sum of the encoded denominator lengths is bounded by the input length. Multiplying by an input numerator still produces an integer of \(O(L)\) bits. Constructing the common denominator and scaled integers using schoolbook arithmetic therefore fits the stated \(O((\tau+1)L^2)\) bound.
A committee certificate contains at most \(\min(K,m)\) candidate identifiers, so its length is polynomial even when \(K\) is encoded in binary. Checking membership in \(C\), distinctness, the size bound, and represented types is polynomial. The sums being compared also have \(O(L)\) bits: summing at most \(\tau\) integers adds at most \(O(\log\tau)\) bits, which is absorbed by \(O(L)\).
The stated verification bound \(O((m+p\tau+1)L^2)\) is conservative and sufficient. Membership in \(\mathrm{NP}\) is established.
The cited source defines the decision version using at most \(K\) selected sets and an integer coverage threshold. Its Theorem 1 states \(\mathrm{W[1]}\)-completeness for every constant frequency bound greater than \(2\), parameterized by the number of selected sets. Its discussion of MaxVertexCover also supports classical \(\mathrm{NP}\)-hardness with frequency bound \(2\). These are precisely the source formulations needed here. [Skowron–Faliszewski, Sections 2–4](https://arxiv.org/html/1309.4405)
The prover states the relevant frequency restrictions and parameter explicitly. No additional source hypothesis is left unchecked.
The trivial branches are correct. With an empty candidate set and only the empty approval type, every committee represents mass \(0\). Threshold \(0\) therefore gives a yes-instance, and threshold \(1\) gives a no-instance, independently of \(K\). These branches also handle an empty source universe.
For the remaining branch, \(n\ge1\) and \(1\le t\le n\). The chosen denominator satisfies \(n\le D<2n\), including \(n=1\).
Each element induces an approval type of size at most \(p\). Grouping equal types ensures that support entries are distinct. Every listed nonempty type has positive mass, and the empty-type numerator \(c_\varnothing+D-n\) is nonnegative. Omitting that type when its numerator is zero satisfies the strict positivity requirement.
The displayed normalization calculation is correct. Padding contributes only to the empty type, which is allowed by the task and is never represented. All constructed masses are dyadic.
The support-size and encoding bounds are valid: at most \(n\) types arise from source elements, and padding can introduce at most one additional type. Numerators and denominator require \(O(\log(n+1))\) bits. Because the source universe is explicit, grouping and constructing the output take polynomial time in its input length.
The elementwise equivalence between source coverage and approval-type intersection is exact. Grouping preserves multiplicities through \(c_A\), and empty-type padding contributes no represented mass. Hence the represented mass equals the source coverage count divided by \(D\).
Since the threshold is \(t/D\), the decision answers coincide. The committee bound remains exactly \(K\).
Consequently, the frequency-\(2\) source establishes \(\mathrm{NP}\)-hardness for every fixed \(p\ge3\). Together with membership, this proves \(\mathrm{NP}\)-completeness.
The fixed-frequency-\(p\) parameterized source establishes \(\mathrm{W[1]}\)-hardness through a polynomial, parameter-preserving reduction. The conditional exclusion of an exact \(f(K)\operatorname{poly}(m,\tau,L)\)-time algorithm follows. The prover correctly avoids claiming \(\mathrm{W[1]}\)-membership for the weighted formulation.
Removing candidates outside \(R\) preserves represented mass. Monotonicity justifies extending any committee in \(R\) of size at most \(k=\min(K,r)\) to size exactly \(k\). Therefore enumerating the \(\binom{r}{k}\) committees is sufficient.
Both stated running-time bounds are valid. The simplified bound follows from \(\binom{r}{k}\le(r+1)^K\) and \(r\le\min(m,p\tau)\). The cases \(K=0\) and \(r=0\) each require examining the single empty committee and are included.
The threshold and committee boundary statements are also correct. In particular, selecting all candidates in \(R\) represents exactly the total mass of nonempty approval types, namely \(1-\mu_\varnothing\).
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.