Answer: \(\mathrm{NP}\)-complete, even with equal masses and endowments and requirements in \(\{0,1\}\); \(\mathrm{W[1]}\)-hard parameterized by \(\tau\), hence not FPT unless \(\mathrm{FPT}=\mathrm{W[1]}\).
Theorem 8.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateSC is W[1]-hard when parameterized by $|C|$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given goals \(G\), resources \(R\), and a distribution \(\mu\) over \(\tau\) types, where each type \(t\) has an acceptable-goal set \(A_t\subseteq G\) and per-agent endowments \(e_{t,r}\), and each goal \(g\) has population-normalized requirements \(q_{g,r}\), determine whether there is a nonempty goal set \(S\subseteq G\) such that \(A_t\cap S\neq\emptyset\) for every type with \(\mu_t>0\), and \(\sum_{g\in S}q_{g,r}\leq\sum_t\mu_t e_{t,r}\) for every resource \(r\in R\).
Let \(G\) be a finite goal set with \(m=|G|\), and let \(R\) be a finite nonempty resource set. The entire society is the coalition under consideration.
A society is given by its support: the list of the \(\tau\geq1\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types; \(\sum_t\mu_t=1\).
Each type has an acceptable-goal set \(A_t\subseteq G\), possibly empty, and per-agent endowments \(e_{t,r}\in\mathbb{Q}_{\geq0}\). Each goal has population-normalized requirements \(q_{g,r}\in\mathbb{Q}_{\geq0}\); all numerical inputs are binary encoded.
Goals are indivisible and selected once. A successful selection is a nonempty set \(S\subseteq G\) satisfying \(A_t\cap S\neq\emptyset\) for every support type and \(\sum_{g\in S}q_{g,r}\leq\sum_t\mu_t e_{t,r}\) for every \(r\in R\).
Let \(L\) be the total input bit length; state running times in \(m,\tau,|R|,L\).
Is deciding whether a successful selection exists in \(\mathrm{P}\), or is it NP-hard? If NP-hard, is it FPT parameterized by \(\tau\)?
For finite agent lists, Successful Coalition is strongly NP-complete, even with endowments and requirements in \(\{0,1\}\) ([Wooldridge–Dunne](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aij2006a.pdf)), and is \(\mathrm{W[1]}\)-hard parameterized by coalition size ([Chitnis–Hajiaghayi–Liaghat](https://arxiv.org/pdf/1105.0707)).
No result settling this exact mass formulation was located in the literature search.
The problem is \(\mathrm{NP}\)-complete, even when every endowment equals \(1\), every requirement belongs to \(\{0,1\}\), and all support types have equal mass.
Parameterized by the support size \(\tau\), it is \(\mathrm{W[1]}\)-hard. Thus it is not FPT unless \(\mathrm{FPT}=\mathrm{W[1]}\). It does admit an XP algorithm with running time
\(O\!\left(m^\tau\tau(\tau+|R|)L^2\right)\) for \(m\geq1\).
These are complexity classifications with the usual qualifications: polynomial-time solvability would imply \(\mathrm{P}=\mathrm{NP}\), and fixed-parameter tractability would imply \(\mathrm{FPT}=\mathrm{W[1]}\).
Define the aggregate budget for resource \(r\) by
\(B_r=\sum_{t=1}^{\tau}\mu_t e_{t,r}\).
A certificate is the \(m\)-bit indicator vector of a selected set \(S\). Verification checks that:
All arithmetic can be performed exactly. For each resource, the products and sums have intermediate numerator and denominator lengths \(O(L)\): their denominators can be taken as products of the relevant input denominators, whose total bit lengths are bounded by \(O(L)\). Numerator lengths satisfy the same bound, including the additional logarithmic cost of summation.
Using elementary integer arithmetic, verification therefore takes
\(O\!\left(((m+\tau)|R|+m\tau+1)L^2\right)\)
bit operations. Hence the problem belongs to \(\mathrm{NP}\).
If \(m=0\), or some \(A_t\) is empty, the instance is immediately unsuccessful. The hardness construction below avoids both cases.
We use the standard facts that Independent Set is \(\mathrm{NP}\)-complete and is \(\mathrm{W[1]}\)-complete when parameterized by the requested set size \(k\). Independent Set is also the parameterized source problem used in [Chitnis–Hajiaghayi–Liaghat, Theorem 5.1](https://arxiv.org/pdf/1105.0707). We give the reduction for the mass formulation explicitly.
Let \(H=(V,E)\) be a finite simple undirected graph, with \(n=|V|\), and let \(1\leq k\leq n\). The excluded cases are decidable immediately, so this restriction preserves both hardness statements.
Create exactly \(k\) support types, indexed by \(i\in\{1,\ldots,k\}\), each with mass \(\mu_i=1/k\).
For every index \(i\) and vertex \(v\), create a goal \(g_{i,v}\). Define
\(A_i=\{g_{i,v}:v\in V\}\).
These acceptable-goal sets are nonempty and pairwise disjoint. Consequently the listed types are distinct and the support size is exactly \(\tau=k\).
Create one resource \(r_v\) for every vertex \(v\), and one resource \(r_e\) for every edge \(e\). Thus
\(m=kn\) and \(|R|=n+|E|\).
In particular, \(R\neq\emptyset\).
Give every type one unit of every resource:
\(e_{i,r}=1\).
Since the masses sum to one, every aggregate budget is
\(B_r=\sum_{i=1}^{k}(1/k)\cdot1=1\).
Set the requirements as follows:
Every requirement belongs to \(\{0,1\}\). All masses are positive binary-encoded rationals, with total mass one.
Suppose \(H\) has an independent set \(\{v_1,\ldots,v_k\}\). Select
\(S=\{g_{1,v_1},\ldots,g_{k,v_k}\}\).
This nonempty set intersects every \(A_i\).
For each vertex resource \(r_v\), its total requirement is at most \(1\), because the chosen vertices are distinct. For an edge resource \(r_{\{u,w\}}\), its total requirement is the number of selected vertices among \(u,w\). Independence makes this number at most \(1\).
All requirements therefore satisfy their budgets, so \(S\) is successful.
Suppose a successful selection \(S\) exists. Since \(S\cap A_i\neq\emptyset\), choose one representative \(g_{i,v_i}\in S\cap A_i\) for each \(i\).
The vertices \(v_i\) are distinct. Indeed, if \(v_i=v_j=v\) for distinct indices, the two distinct selected goals would together require \(2\) units of \(r_v\), exceeding its budget \(1\).
They are also pairwise nonadjacent. If \(\{v_i,v_j\}\in E\), those two selected goals would together require \(2\) units of \(r_{\{v_i,v_j\}}\), again exceeding budget \(1\).
Thus \(\{v_1,\ldots,v_k\}\) is an independent set of size \(k\).
The construction lists \(kn\) goals, \(k\) types, and \(n+|E|\) resources. Its requirement table has \(kn(n+|E|)\) entries, each equal to \(0\) or \(1\). The only nonintegral values are the masses \(1/k\), whose numerator and denominator require \(O(\log(k+1))\) bits.
Because \(k\leq n\), the construction has polynomial size and can be produced in polynomial time. Together with membership in \(\mathrm{NP}\), the equivalence proves \(\mathrm{NP}\)-completeness.
Moreover, the output parameter is exactly \(\tau=k\). The same construction is therefore a parameterized reduction proving \(\mathrm{W[1]}\)-hardness with respect to \(\tau\).
Lemma. If a successful selection exists, one exists containing at most \(\tau\) goals.
Proof. Let \(S\) be successful. For every support type \(t\), choose a goal \(g_t\in A_t\cap S\), and let \(S'=\{g_t:1\leq t\leq\tau\}\).
Since \(\tau\geq1\), the set \(S'\) is nonempty. It satisfies every type, and \(|S'|\leq\tau\). Furthermore, \(S'\subseteq S\), so nonnegativity of every requirement gives
\(\sum_{g\in S'}q_{g,r}\leq\sum_{g\in S}q_{g,r}\leq B_r\)
for every \(r\). Hence \(S'\) is successful. \(\square\)
This yields an exact algorithm:
Every tuple automatically satisfies all types. The lemma proves that a successful instance is accepted by some tuple.
There are at most \(m^\tau\) tuples. Pairwise comparison removes duplicates in \(O(\tau^2)\) comparisons, and resource checking uses \(O(\tau|R|)\) rational additions and comparisons. Including preprocessing, a valid bit-operation bound is
\(O\!\left(m^\tau\tau(\tau+|R|)L^2\right)\)
for \(m\geq1\).
Thus every fixed value of \(\tau\) gives a polynomial-time algorithm. This is an XP bound: its polynomial exponent depends on \(\tau\). The parameter-preserving hardness reduction rules out an FPT bound \(f(\tau)L^c\), with constant \(c\), unless \(\mathrm{FPT}=\mathrm{W[1]}\).
⟨structured verdict parsed — rendered above⟩
The prover’s output fully resolves the task. The explicit reduction establishes \(\mathrm{NP}\)-completeness and \(\mathrm{W[1]}\)-hardness parameterized by support size \(\tau\). The verification and XP running-time bounds are valid. No major or minor mathematical issues were found.
The proposed certificate specifies a subset of goals, and the three verification conditions exactly match the task: nonemptiness, satisfaction of every positive-mass type, and feasibility for every resource.
The intermediate bit-length claim is correct. Each budget uses products of input rationals; a common denominator can be formed from the corresponding input denominators, whose combined bit lengths are bounded by \(O(L)\). The same holds for selected-goal requirement sums. Numerators also have \(O(L)\) bits, including summation overhead. Elementary arithmetic therefore supports the stated bound
\[
O\!\left(((m+\tau)|R|+m\tau+1)L^2\right).
\]
This proves membership in \(\mathrm{NP}\).
The immediate rejection cases are correct. If \(m=0\), no nonempty selection exists. If an acceptable-goal set is empty, its positive-mass support type cannot be satisfied.
The source problem is Independent Set on finite simple undirected graphs, with requested size \(k\). Its stated classical and parameterized hardness classifications apply to this formulation.
The attribution to Chitnis–Hajiaghayi–Liaghat is accurate: Theorem 5.1 uses Independent Set parameterized by the requested independent-set size as its source. The prover supplies its own mass-formulation reduction, so it does not rely on transferring the finite-agent theorem without justification. [Chitnis–Hajiaghayi–Liaghat, Theorem 5.1](https://arxiv.org/pdf/1105.0707)
Restricting to \(1\leq k\leq n\) preserves hardness: the excluded cases are directly decidable and introduce no substantive restriction on the hard instances.
All constructed data satisfy the task’s domain restrictions:
Encoding \(1/k\) as a binary rational requires only \(O(\log(k+1))\) bits; no finite binary expansion assumption is needed.
An independent set of size \(k\) supplies one goal for each support type. The selection is nonempty and satisfies every type.
Distinct selected vertices consume at most one unit of each vertex resource. Independence ensures that at most one endpoint of any edge is selected, so each edge resource also receives total requirement at most one. Both feasibility checks match the constructed budgets.
A successful selection contains a representative goal from every acceptable-goal set. Pairwise disjointness makes representatives for different types distinct goals.
If two representatives encode the same vertex, their combined requirement for that vertex resource is two, contradicting budget one. If they encode adjacent vertices, their combined requirement for the corresponding edge resource is likewise two.
Additional goals in the successful selection cannot invalidate these contradictions because all requirements are nonnegative. Thus the representatives yield \(k\) distinct, pairwise nonadjacent vertices. The reverse implication is sound.
The counts \(m=kn\) and \(|R|=n+|E|\) are correct. The requirement table has \(kn(n+|E|)\) entries. The endowment table, acceptable-goal lists, and mass encodings also have polynomial size when \(k\leq n\).
Consequently, the construction is a polynomial-time many-one reduction. Together with membership in \(\mathrm{NP}\), it proves the claimed restricted \(\mathrm{NP}\)-completeness.
It is also a valid parameterized reduction: its running time is polynomial in the source input size, and its output parameter is exactly \(\tau=k\). This establishes \(\mathrm{W[1]}\)-hardness. The conditional conclusion that an FPT algorithm would imply \(\mathrm{FPT}=\mathrm{W[1]}\) is correct.
The witness lemma correctly selects one acceptable goal per support type and takes their union. This union is nonempty because \(\tau\geq1\), has size at most \(\tau\), and satisfies every type. Its feasibility follows from containment in the original successful selection and nonnegative requirements.
Enumerating tuples with \(g_t\in A_t\) is therefore complete. Taking distinct goals is essential because goals are selected once; the algorithm explicitly does so.
There are at most \(m^\tau\) tuples. Duplicate removal and resource verification fit the stated bound
\[
O\!\left(m^\tau\tau(\tau+|R|)L^2\right)
\]
for \(m\geq1\). Preprocessing is absorbed by this bound. For every fixed \(\tau\), the running time is polynomial, so the XP classification is correct.
No repair or additional clarification is required. The answer addresses the exact support-and-mass formulation and properly qualifies its negative FPT conclusion by the standard complexity-class assumption.
⟨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.