Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W}[2]\)-complete parameterized by \(k\); an \(\mathrm{FPT}\) algorithm in \(k\) exists if and only if \(\mathrm{FPT}=\mathrm{W}[2]\).
Theorem 14 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatek-Perfect-GASP is W[2]-hard. It remains to be W[2]- hard even if all agents have increasing preferences or all agents have decreasing preferences.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite activity set \(A\), a finite type set \(T\) with positive binary-rational masses \(\mu_t\) summing to \(1\), activity approvals \(B_t \subseteq A\), and an integer \(k\), does there exist \(x_{t,a} \ge 0\) such that \(\sum_{a \in A} x_{t,a} = \mu_t\) for every \(t\), \(x_{t,a}=0\) whenever \(a \notin B_t\), and exactly \(k\) activities have positive total mass \(\sum_{t \in T} x_{t,a}\)? What is the parameterized complexity with parameter \(k\)?
Let \(A\) be a finite set of non-void activities, with \(m=|A|\). A society is given by its support: the list \(T\) of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
Each type has an explicitly listed approval set \(B_t\subseteq A\), possibly empty; approval is independent of activity mass. Approved activities are equally preferred to nonparticipation. The input also contains a binary-encoded integer \(k\geq 0\); let \(L\) be the total input bit length.
A perfect mass assignment consists of real numbers \(x_{t,a}\geq 0\) satisfying \(\sum_{a\in A}x_{t,a}=\mu_t\) for every \(t\), and \(x_{t,a}=0\) whenever \(a\notin B_t\). Types may split their mass among activities; no mass may remain unassigned. An activity is used exactly when \(\sum_{t\in T}x_{t,a}>0\).
Is deciding whether a perfect mass assignment uses exactly \(k\) activities in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? If it is \(\mathrm{NP}\)-hard, can it nevertheless be solved in \(\mathrm{FPT}\) time with parameter \(k\)? State running times in \(m,\tau,L,k\).
For indivisible agents, perfect assignment using exactly \(k\) activities is known to be \(\mathrm{NP}\)-hard and \(\mathrm{W}[2]\)-hard parameterized by \(k\), with the latter hardness holding even for approvals independent of group size ([Lee and Williams](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p353.pdf)).
No result settling this exact mass-assignment problem was located in the literature search.
The problem is \(\mathrm{NP}\)-complete and, parameterized by \(k\), \(\mathrm{W}[2]\)-complete. Thus it has an \(\mathrm{FPT}\) algorithm with parameter \(k\) if and only if \(\mathrm{FPT}=\mathrm{W}[2]\).
Divisibility makes assignment to a specified set of activities easy, but selecting that set remains a Set Cover problem.
Define the set of activities with approval support by
\(A^{+}=\bigcup_{t\in T}B_t\), and write \(u=|A^{+}|\).
Lemma. For any \(S\subseteq A\), a perfect mass assignment whose used activities are exactly \(S\) exists if and only if:
Proof. Suppose such an assignment exists. Every used activity receives positive mass from some type that approves it, so \(S\subseteq A^{+}\). For every type \(t\), its positive mass \(\mu_t\) must be assigned among approved activities in \(S\). Hence \(B_t\cap S\neq\varnothing\).
Conversely, suppose the two conditions hold. Put \(d_t=|B_t\cap S|\), which is positive, and define
\(x_{t,a}=\mu_t/d_t\) for \(a\in B_t\cap S\), and \(x_{t,a}=0\) otherwise.
Each type assigns precisely its mass, since
\(\sum_{a\in A}x_{t,a}=d_t(\mu_t/d_t)=\mu_t\).
All positive assignments are approved. Moreover, each \(a\in S\) belongs to some \(B_t\), and therefore receives the positive amount \(\mu_t/d_t\). Activities outside \(S\) receive zero mass. This proves the lemma.
The construction uses rational numbers even though the definition allows real numbers.
If any \(B_t\) is empty, no perfect assignment exists. Also, \(k=0\) is impossible because the total mass is one, and \(k>u\) is impossible because unsupported activities cannot be used.
Assume henceforth that every approval set is nonempty. Define
\(\gamma=\min\{|S|:S\subseteq A^{+},\ B_t\cap S\neq\varnothing\text{ for every }t\in T\}\).
This minimum exists because \(A^{+}\) itself intersects every approval set.
Proposition. A perfect assignment using exactly \(k\) activities exists precisely when
\(\gamma\leq k\leq u\).
Proof. Necessity follows from the lemma. For sufficiency, take a set \(S_0\) attaining \(\gamma\). Since \(k\leq u\), extend \(S_0\) to a subset \(S\subseteq A^{+}\) of cardinality \(k\). Adding activities preserves every nonempty intersection \(B_t\cap S_0\). The lemma then constructs an assignment using exactly \(S\).
Thus the feasible numbers of used activities form an integer interval.
Equivalently, for each activity define
\(C_a=\{t\in T:a\in B_t\}\).
Then \(\gamma\) is the minimum number of sets from the family \((C_a)_{a\in A^{+}}\) whose union is \(T\). This is Set Cover with universe size \(\tau\) and \(u\) available sets.
We use the standard result that Set Cover is \(\mathrm{NP}\)-complete and is \(\mathrm{W}[2]\)-complete when parameterized by the number of selected sets. These classifications are stated in the introduction of [Lin, Ren, Sun, and Wang](https://arxiv.org/html/2202.04377).
Consider a Set Cover instance with universe \(U\), an explicitly listed family \(F_1,\ldots,F_r\subseteq U\), and budget \(q\). The question is whether at most \(q\) sets cover \(U\).
Polynomial-time preprocessing handles an empty universe, zero budget, or an element belonging to no set. Delete empty sets and replace \(q\) by \(\min(q,r)\). Consequently, for the remaining instances we may assume:
Any cases decided during preprocessing can be mapped to fixed mass-assignment yes or no instances with parameter one. For example, use one activity, one type of mass one, and \(k=1\), with approval set either the singleton activity or the empty set. Their parameter is bounded by \(q+1\).
Create activities \(a_1,\ldots,a_r\). For each element \(v\in U\), define its incidence approval set
\(B(v)=\{a_i:v\in F_i\}\).
Create one type for each distinct set among the \(B(v)\). This respects the requirement that \(\tau\) counts supported types; duplicated incidence patterns are merged. Denote the resulting distinct approval sets by \(B_1,\ldots,B_\tau\). Every one is nonempty.
To obtain positive masses with short binary encodings, let
\(b=\lceil\log_2\tau\rceil\), and set
\(\mu_i=2^{-b}\) for \(1\leq i<\tau\), and
\(\mu_\tau=(2^b-\tau+1)/2^b\).
These are positive dyadic rationals because \(2^b\geq\tau\). Their sum is
\(((\tau-1)+(2^b-\tau+1))/2^b=1\).
Each mass needs \(O(\log(\tau+1))\) bits. Set the output budget to \(k=q\).
Every activity has approval support: \(F_i\neq\varnothing\) implies that some element’s type approves \(a_i\). Thus \(A^{+}=A\).
Forward implication. If at most \(q\) source sets cover \(U\), their corresponding activities intersect every \(B(v)\), and hence every supported approval set. Extend these activities to exactly \(q\) activities, which is possible because \(q\leq r\). The lemma gives a perfect mass assignment using exactly those activities.
Reverse implication. If a perfect assignment uses exactly \(q\) activities, the lemma says that those activities intersect every supported approval set. Since each \(B(v)\) equals one of those approval sets, every \(v\in U\) belongs to a corresponding selected source set. Those \(q\) sets cover \(U\).
The construction has \(m=r\), \(\tau\leq|U|\), and polynomial output bit length. It is computable in polynomial time, and the nontrivial construction preserves \(k=q\). Therefore it proves both \(\mathrm{NP}\)-hardness and parameterized \(\mathrm{W}[2]\)-hardness.
For membership in \(\mathrm{NP}\), a certificate is simply a list of \(k\) distinct activities. After rejecting \(k>m\), its length is polynomial in the input size. The verifier checks the two conditions in the lemma; no real-valued certificate is needed.
For membership in \(\mathrm{W}[2]\), first handle the elementary rejection cases. Otherwise, construct Set Cover with universe \(T\), sets \(C_a\) for \(a\in A^{+}\), and budget \(k\). By Section 2, this instance has a cover of size at most \(k\) exactly when the original instance admits an assignment using exactly \(k\) activities. This is a polynomial-time, parameter-preserving reduction.
Consequently, the problem is \(\mathrm{NP}\)-complete and \(\mathrm{W}[2]\)-complete. In particular:
The second statement is conditional on a standard complexity-class separation; no unconditional separation is claimed.
Enumeration by the requested number of activities. After preprocessing, enumerate all \(k\)-element subsets of \(A^{+}\). For each subset, check whether it intersects every approval set.
Using a dense approval table, preprocessing and verification take
\(O(L+m\tau+\binom{u}{k}k\tau)\)
word-RAM operations. A standard word size of \(O(\log(L+m+\tau+2))\) bits suffices. In particular, a bit-complexity bound is
\(\binom{m}{k}(L+m+\tau)^{O(1)}\),
and hence
\(m^k(L+m+\tau)^{O(1)}\)
for \(m\geq1\).
Elementary rejection cases are handled before enumeration, so a very large binary-encoded \(k\) causes no iteration proportional to its value. This is an \(\mathrm{XP}\) algorithm parameterized by \(k\), and is polynomial for every fixed \(k\).
Dynamic programming by support size. The problem is nevertheless \(\mathrm{FPT}\) parameterized by \(\tau\).
Order the activities as \(a_1,\ldots,a_m\). Let \(D_j(V)\) be the minimum number of activities among the first \(j\) whose covered-type union is exactly \(V\subseteq T\), or infinity if no such selection exists.
Initialize \(D_0(\varnothing)=0\) and all other entries to infinity. For every finite entry \(D_j(V)\), update the next layer by:
Every selection either omits or includes the next activity, so induction on \(j\) proves this recurrence computes the stated minima. At termination, \(D_m(T)=\gamma\). Compare it with \(k\), also checking \(k\leq u\).
There are \(2^\tau\) states per layer and two transitions per state. Including mask operations and input processing, the bit running time is
\(2^\tau(L+m+\tau)^{O(1)}\).
As a further easy case, when all approval sets are nonempty, choosing one approved activity per type proves \(\gamma\leq\tau\). Therefore every instance with \(\tau\leq k\leq u\) is a yes-instance.
The divisible problem’s hardness thus follows directly from approval incidence, rather than from group-size preferences. This also matches the incidence structure used in the indivisible reduction in [Lee and Williams, Theorem 14](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p353.pdf).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The characterization of feasible activity sets, both complexity reductions, and the algorithmic bounds are sound. I found no major or minor mathematical issues requiring repair.
In the necessity direction, a used activity receives positive mass from at least one type because the support is finite and assignments are nonnegative. The approval restriction then places that activity in \(A^{+}\). Each supported type has strictly positive mass, so its row-sum constraint forces a positive assignment to an approved activity in \(S\).
In the sufficiency direction, the intersection condition gives \(d_t=|B_t\cap S|\geq 1\), making every division well-defined. The proposed entries are nonnegative, satisfy each row-sum constraint, and respect approvals. For each \(a\in S\), the condition \(S\subseteq A^{+}\) supplies a supported type approving \(a\); that type contributes the strictly positive amount \(\mu_t/d_t\). Thus every activity in \(S\), and no activity outside it, is used.
The argument correctly uses divisibility and imposes no unsupported activity-capacity constraint. The rational construction also confirms that allowing real assignments creates no certificate difficulty.
An empty approval set makes the corresponding positive-mass row impossible to assign. Total mass one excludes \(k=0\). Unsupported activities cannot be used, so \(k>u\) is impossible.
Under the stated assumption that every approval set is nonempty, \(A^{+}\) is a feasible hitting set. Consequently, the finite minimum defining \(\gamma\) exists. If \(\gamma\leq k\leq u\), a minimizing set can be extended to cardinality \(k\) inside \(A^{+}\), preserving all intersections. The lemma then guarantees strictly positive use of every added activity. This establishes the claimed interval of feasible cardinalities.
A valid society necessarily has \(\tau\geq 1\), since its positive masses sum to one. If \(m=0\), all approval sets are empty, so the rejection rule also covers that case.
For \(C_a=\{t\in T:a\in B_t\}\), selecting activities intersecting every approval set is exactly selecting sets \(C_a\) whose union is \(T\). The universe has size \(\tau\), as required by the task’s support-based encoding. Neither the characterization nor the decision depends on the numerical sizes of the positive masses.
The external result used is that explicitly represented, unweighted Set Cover is \(\mathrm{NP}\)-complete and is \(\mathrm{W}[2]\)-complete parameterized by the selected-set budget. The cited introduction states both classifications. Its formulation uses exactly the requested number of sets; the prover’s normalization \(q\leq r\) and extension argument justify the equivalent at-most-budget formulation used in the reduction. [Lin, Ren, Sun, and Wang](https://arxiv.org/html/2202.04377).
The source instances used here have an explicit finite universe and an explicitly listed family, matching those hypotheses.
The preprocessing correctly decides the exceptional source instances. Deleting empty sets preserves cover feasibility, and capping the budget at the remaining family size preserves the at-most-budget question. Fixed yes/no target instances have parameter one, bounded by \(q+1\), so these branches satisfy the parameterized-reduction requirement.
Merging identical incidence approval sets preserves every covering constraint: two elements with identical incidence patterns impose identical requirements. It also ensures that the constructed support consists of distinct types.
The mass calculation is correct. Since \(\tau\geq 1\), \(b=\lceil\log_2\tau\rceil\) is defined. All assigned masses are positive, and their sum is one. At \(\tau=1\), the construction gives \(b=0\) and the sole mass equals one. Each numerator and denominator has \(O(\log(\tau+1))\) bits.
Nonempty source sets ensure every activity has approval support. Therefore, a cover using at most \(q\) activities can be extended to exactly \(q\), since \(q\leq r\). Conversely, intersecting every distinct supported approval set intersects every original element’s incidence pattern, yielding a source cover.
The output size and construction time are polynomial in the explicit source encoding. The main branch has \(k=q\), and the exceptional branches have bounded parameter. Both \(\mathrm{NP}\)-hardness and \(\mathrm{W}[2]\)-hardness follow.
After rejecting \(k>m\), a list of \(k\) distinct activities is a polynomial-size certificate. The feasibility lemma permits verification using approval incidence alone.
The reverse reduction to Set Cover preserves the parameter \(k\). After the elementary rejection cases, Section 2 establishes precisely the equivalence needed between a cover of size at most \(k\) and an assignment using exactly \(k\).
Thus both completeness claims follow. The polynomial-time and parameter-\(k\) FPT equivalences are correctly conditional; the prover does not claim an unconditional separation of complexity classes.
The dense-table enumeration bound accounts for input processing, table construction, and at most \(k\tau\) incidence checks per candidate. The stated word size suffices for indices and counters. The polynomial bit overhead yields the claimed \(\mathrm{XP}\) bound. Rejecting oversized binary-encoded \(k\) before enumeration avoids iteration proportional to an arbitrarily large budget.
The dynamic program’s state records the exact covered-type union. Its include/omit transitions exhaust the possibilities for the next activity, and taking minimum costs preserves the stated invariant. Under the earlier nonempty-approval assumption, \(D_m(T)=\gamma\). The final comparison must, and does, include \(k\leq u\).
There are \(2^\tau\) states per layer; mask and cost operations require polynomial bit overhead. Hence \(2^\tau(L+m+\tau)^{O(1)}\) is valid. The additional bound \(\gamma\leq\tau\) also follows from the selection described in the output.
Lee and Williams’ Theorem 14 uses closed-neighborhood approval incidence and preferences independent of group size, consistent with the prover’s comparison. That theorem is contextual support; the mass-assignment hardness is established by the prover’s own reduction. [Lee and Williams, Theorem 14](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p353.pdf).
No additional mathematical clarification 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.