Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateconsiders a single task requiring any number of skills. We now show that OPT-CS is NP-complete even when tasks require at most two skills, through a reduction from NEGATIVE-CUT, another known NP-complete problem (Deng and Papadim- itriou 1994).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a required skill set \(S\), support types \(t=1,\ldots,\tau\) with skill bundles \(A_t\subseteq S\), positive rational masses \(\mu_t\) summing to one, and a rational threshold \(\rho\), let \(\mathcal Q\) be the inclusion-minimal type sets whose bundles cover \(S\). Does the LP maximizing \(\sum_{Q\in\mathcal Q}x_Q\), subject to \(x_Q\ge 0\) and \(\sum_{Q\ni t}x_Q\le\mu_t\) for every type \(t\), have optimum at least \(\rho\)?
Let \(S\) be a nonempty required skill set, with \(m=|S|\). A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types. Type \(t\) has a skill bundle \(A_t\subseteq S\) and mass \(\mu_t>0\), with \(\sum_{t=1}^{\tau}\mu_t=1\). The threshold is \(\rho\in\mathbb Q\).
Let \(\mathcal Q\) consist of all inclusion-minimal subsets \(Q\subseteq\{1,\ldots,\tau\}\) satisfying \(\bigcup_{t\in Q}A_t=S\). This family is specified implicitly by the bundles, not supplied as an enumerated list.
Define \(V=\max\{\sum_{Q\in\mathcal Q}x_Q:x_Q\in\mathbb R_{\ge0},\ \sum_{Q\ni t}x_Q\le\mu_t\text{ for every }t\}\). Unused mass is permitted; if \(\mathcal Q=\varnothing\), set \(V=0\). Let \(L\) be the total binary input length, including the bundles, masses, and threshold.
Is deciding whether \(V\ge\rho\) solvable in time polynomial in \(m\), \(\tau\), and \(L\), or is it NP-hard?
For finite agents, partitioning them into coalitions to maximize the number whose combined skills cover a nonempty required skill set is NP-complete in its threshold decision form, even when the threshold is \(2\).
Deciding whether \(V\ge\rho\) is \(\mathrm{NP}\)-complete under polynomial-time many-one reductions. Consequently, it has no algorithm polynomial in \(m,\tau,L\) unless \(\mathrm{P}=\mathrm{NP}\).
The proof uses fractional graph coloring, so it establishes hardness of the fractional problem directly.
Let \(\mathcal C\) denote all subsets of types whose bundles cover \(S\), including covers that are not inclusion-minimal.
The packing optimum over \(\mathcal C\) equals \(V\). Indeed, every \(C\in\mathcal C\) contains an inclusion-minimal cover \(Q(C)\subseteq C\). Given a feasible packing over \(\mathcal C\), transfer the entire weight on each \(C\) to \(Q(C)\), adding weights when necessary. This preserves the objective and cannot increase the load on any type. Conversely, every packing over \(\mathcal Q\) is a packing over \(\mathcal C\).
Thus we may work with all covers.
Let \(G=(U,E)\) be a finite simple graph with at least one edge. Write \(\mathcal I(G)\) for its independent sets and define its fractional chromatic number by
\[ c=\chi_f(G) =\min\left\{\sum_{I\in\mathcal I(G)}w_I: w_I\ge0,\quad \sum_{I\ni v}w_I\ge1\text{ for every }v\in U \right\}. \]
This minimum is attained: singleton independent sets give a feasible solution of value \(|U|\), and restricting the objective to at most \(|U|\) gives a nonempty compact feasible region. Moreover, \(c\ge2\): for the endpoints of any edge, their coverage requirements sum to at least \(2\), while each independent set contains at most one endpoint.
Let \(T(G)\) be the maximum fractional packing of vertex covers with unit capacity at each vertex:
\[ T(G)= \max\left\{\sum_{C}z_C: z_C\ge0,\quad \sum_{C\ni v}z_C\le1\text{ for every }v\in U \right\}, \]
where \(C\) ranges over all vertex covers of \(G\).
Claim. \(T(G)=c/(c-1)\).
Lower bound. Take an optimal fractional coloring \(w\). The complement \(U\setminus I\) of every independent set is a vertex cover. Assign it weight
\[ z_{U\setminus I}=\frac{w_I}{c-1}. \]
For each vertex \(v\), its packing load is
\[ \sum_{C\ni v}z_C =\frac{c-\sum_{I\ni v}w_I}{c-1} \le1. \]
This packing has total weight \(c/(c-1)\).
Upper bound. Consider any feasible vertex-cover packing of total weight \(\lambda\). If \(\lambda\le1\), then \(\lambda\le c/(c-1)\).
If \(\lambda>1\), assign each independent set \(U\setminus C\) weight
\[ w_{U\setminus C}=\frac{z_C}{\lambda-1}. \]
Its coverage of a vertex \(v\) is
\[ \sum_{I\ni v}w_I =\frac{\lambda-\sum_{C\ni v}z_C}{\lambda-1} \ge1. \]
Hence this is a fractional coloring of total weight \(\lambda/(\lambda-1)\), so
\[ c\le\frac{\lambda}{\lambda-1}. \]
Since \(c>1\) and \(\lambda>1\), rearranging gives \(\lambda\le c/(c-1)\). This proves the claim.
We use the known theorem that, for every fixed rational \(r>2\), deciding whether \(\chi_f(G)\le r\) is \(\mathrm{NP}\)-hard. In particular, this holds for \(r=3\). The theorem is explicitly stated in the proof of Observation 3 of [Hochstättler, Schröder, and Steiner, *On the Complexity of Digraph Colourings and Vertex Arboricity*](https://dmtcs.episciences.org/6020/pdf).
We may restrict the source problem to graphs with at least one edge: edgeless graphs are yes-instances and can be mapped to a fixed graph consisting of one edge.
Given such a graph \(G=(U,E)\), let \(n=|U|\), and let \(N\) be the smallest power of two satisfying \(N\ge n\). Construct the society as follows:
The masses are positive and sum to \(1\). They and the threshold are dyadic rationals with \(O(\log n)\)-bit representations.
A subset of vertex types covers \(S\) precisely when the corresponding vertices form a vertex cover. The additional empty-bundle type belongs to no inclusion-minimal cover, since deleting it preserves coverage.
By Section 1 and scaling all vertex capacities from \(1\) to \(1/N\),
\[ V=\frac{T(G)}{N} =\frac{1}{N}\frac{\chi_f(G)}{\chi_f(G)-1}. \]
Writing \(c=\chi_f(G)\ge2\), we obtain
\[ V\ge\rho \quad\Longleftrightarrow\quad \frac{c}{c-1}\ge\frac32 \quad\Longleftrightarrow\quad 2c\ge3(c-1) \quad\Longleftrightarrow\quad c\le3. \]
Thus the construction preserves yes- and no-instances.
The construction lists at most \(n+1\) types and \(|E|\) skills. Its bundles, masses, and threshold have polynomial total encoding length. It never enumerates minimal covers.
If types must have distinct bundles. Merge types with identical bundles and add their masses. This preserves \(V\): a minimal cover uses at most one type from each identical-bundle group, so merging preserves minimal covers and combines their weights. Conversely, split each coalition weight independently among the original representatives, in proportion to their masses. A representative receives its mass proportion of the merged group’s load, so its capacity is respected. All merged masses remain positive dyadic rationals, and support size cannot increase.
Therefore the stated decision problem is \(\mathrm{NP}\)-hard.
We also prove membership in \(\mathrm{NP}\), despite the implicit coalition family.
Let \(M\) be the type–coalition incidence matrix, with one column for each \(Q\in\mathcal Q\). Introducing slack variables gives
\[ Mx+s=\mu,\qquad x,s\ge0. \]
This is a finite linear program. It is feasible by taking \(x=0\). It is bounded: every coalition is nonempty because \(S\ne\varnothing\), and summing the capacity constraints gives
\[ \sum_{Q\in\mathcal Q}|Q|x_Q\le1, \qquad\text{hence}\qquad \sum_{Q\in\mathcal Q}x_Q\le1. \]
The slack variables are bounded as well. Since the slack columns form an identity matrix, the equality matrix has rank \(\tau\). Standard linear programming therefore supplies an optimal basic feasible solution with at most \(\tau\) positive coalition variables.
Its weights have polynomial bit length. To see this explicitly, write \(\mu_t=a_t/b_t\) and put \(D=\prod_t b_t\). The bit length of \(D\) is \(O(L)\). A basis matrix \(B\) is a nonsingular \(\tau\times\tau\) matrix with entries in \(\{0,1\}\). For its basic variables, Cramer’s rule gives
\[ x_j=\frac{\det(B_j)}{D\det(B)}, \]
where \(B_j\) replaces one column of \(B\) by \(D\mu\). Because \(0<\mu_t\le1\), Hadamard’s inequality gives
\[ |\det(B)|\le\tau^{\tau/2}, \qquad |\det(B_j)|\le D\tau^{\tau/2}. \]
Each weight consequently requires \(O(L+\tau\log(\tau+1))\) bits.
A certificate lists at most \(\tau\) coalitions and these rational weights. A verifier checks that:
These checks use the explicitly supplied bundles and polynomial-time rational arithmetic. Every yes-instance has such a certificate.
Hence the problem is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The continuous problem is $\mathrm{NP}$-complete under polynomial-time many-one reductions. I found no major or minor mathematical issues.
The argument is valid. Every cover contains an inclusion-minimal cover because the type set is finite. Transferring its weight to a contained minimal cover preserves the objective and weakly decreases every capacity load. The reverse inclusion of feasible packings is immediate.
The argument also handles the case $\mathcal Q=\varnothing$: then no cover exists, so both packing optima are zero.
The definition of $c=\chi_f(G)$ is precise. There are finitely many independent sets, and restricting their nonnegative weights to total weight at most $|U|$ gives a compact, nonempty feasible region. Thus the minimum is attained.
The hypothesis that $G$ has an edge ensures $c\ge2$: adding the coverage constraints for its endpoints gives a requirement of at least two, whereas each independent set contributes to at most one endpoint. In particular, division by $c-1$ is legitimate.
Both directions of the identity
$$
T(G)=\frac{c}{c-1}
$$
check out:
Empty independent sets and isolated vertices cause no exception. An edge ensures that every vertex cover is nonempty, so the packing objective is bounded as well.
The external theorem is stated sufficiently precisely for its application: deciding $\chi_f(G)\le r$ is $\mathrm{NP}$-hard for each fixed rational $r>2$. The proof of Observation 3 in the cited paper explicitly states this hardness result, so the application at $r=3$ is supported. [Hochstättler, Schröder, and Steiner, Observation 3](https://dmtcs.episciences.org/6020/pdf).
The restriction to graphs containing an edge preserves hardness: edgeless graphs are yes-instances at threshold three, and the proposed fixed replacement is also a yes-instance.
The construction satisfies the target’s input requirements:
Covering the edge skills is exactly the vertex-cover condition. The extra empty-bundle type cannot occur in a minimal cover. Consequently, the capacity scaling and Section 1 justify
$$
V=\frac1N\frac{c}{c-1}.
$$
The threshold calculation is correct, including equality:
$$
V\ge\frac{3}{2N}\quad\Longleftrightarrow\quad c\le3.
$$
Thus this is a polynomial-time many-one reduction to the stated continuous problem, without enumerating minimal covers.
The optional merging argument is valid. Minimality prevents a coalition from containing two representatives with identical bundles. Replacing representatives by their merged group preserves coverage and minimality.
Conversely, proportional splitting among representatives preserves total coalition weight and gives each representative its stated proportion of the group’s load. Positivity of the group mass makes these proportions well-defined. This addresses distinct-bundle interpretations of “types” without changing the optimum.
The certificate argument is correct despite the potentially exponential number of columns.
Every coalition is nonempty, so summing capacities gives the stated objective bound. Slack variables are also bounded. The feasible region is therefore a nonempty bounded polyhedron. The standard optimal-basic-solution theorem applies, and the identity slack columns ensure row rank $\tau$. Hence an optimal solution has at most $\tau$ positive coalition variables.
The bit-length calculation is correct. The integer vector $D\mu$ has entries at most $D$, so Hadamard’s inequality gives precisely the displayed determinant bounds. Cramer’s rule then yields polynomial-size rational weights.
The proposed verification checks are sufficient. For coverage, checking every single-type deletion establishes inclusion-minimality because coverage is monotone under adding types. All capacity and threshold comparisons use polynomial-time exact rational arithmetic.
The empty-family case and arbitrary rational thresholds are covered: when $V=0$ and $\rho\le0$, an empty certificate suffices; when $\rho>0$, no feasible certificate can pass.
No repair or additional clarification is required. The argument establishes hardness directly for fractional packing and also proves the stronger claim of $\mathrm{NP}$-completeness.
⟨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.