Answer: \(\mathrm{NP}\)-complete
Theorem 11 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateWhen 𝑠= 2, BCFEA admits a polynomial-time algorithm. Approximation Algorithm.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite agent types \(A\) with rational masses \(\mu_a\), finite job types \(J\) with rational per-capita supplies \(\nu_j\), additive type-dependent utilities and costs \(p_a(j)\) and \(c_a(j)\), a common budget \(B\), and a type-level compatibility relation, decide for rational \(q\) whether nonnegative variables \(y_{a,b}\) assign every agent mass to a compatible bundle \(b\) containing at most two job copies, with \(p_a(b)\ge q\), \(c_a(b)\le B\), \(\sum_b y_{a,b}=\mu_a\), and \(\sum_{a,b}m_j(b)y_{a,b}=\nu_j\) for every \(j\); equivalently, maximize \(q\).
Given finite employee types \(A\) with rational masses \(\mu_a\), job-slot types \(J\) with rational supplies \(\sigma_j\), a conflict graph \(H=(J,F)\), additive utilities \(p_a(S)=\sum_{j\in S}p_a(j)\), additive costs \(c_a(S)=\sum_{j\in S}c_a(j)\), budgets \(B_a\), and target \(P\), let a bundle be an independent set \(S\subseteq J\).
Target. Is it NP-hard or polynomial-time solvable to decide whether nonnegative masses \(y_{a,S}\) exist such that \(\sum_S y_{a,S}=\mu_a\), \(\sum_{a,S:j\in S}y_{a,S}=\sigma_j\), and \(y_{a,S}>0\) implies \(c_a(S)\le B_a\) and \(p_a(S)\ge P\)?
Nearest known results. The discrete BCFEA decision problem is NP-hard for two agents when the conflict graph is disconnected. The result concerns indivisible items allocated as a partition, rather than masses of employee and job-slot types.
Assume all numerical data are rational and encoded in binary. The feasibility problem is \(\mathrm{NP}\)-complete.
Hardness holds even when:
Thus the problem is \(\mathrm{NP}\)-hard, rather than polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
Let \(\mathcal K\) be the family of eligible type–bundle pairs \((a,S)\), meaning that \(S\) is independent in \(H\), \(c_a(S)\le B_a\), and \(p_a(S)\ge P\).
The feasibility constraints form a linear system
\[ Ay=b,\qquad y\ge 0, \]
where columns are indexed by \(\mathcal K\), rows are indexed by \(A\cup J\), and the column for \((a,S)\) has a \(1\) in the row of \(a\), a \(1\) in every row \(j\in S\), and zeroes elsewhere. Hence \(A\) is a zero-one matrix with
\[ r=|A|+|J| \]
rows.
If this system is feasible, its feasible region is bounded: every variable \(y_{a,S}\) satisfies \(0\le y_{a,S}\le \mu_a\). Therefore it has an extreme point. At an extreme point, the columns corresponding to positive variables are linearly independent; otherwise a nonzero dependence vector would permit sufficiently small perturbations in both directions while preserving nonnegativity and all equalities. Consequently, an extreme point has at most \(r\) positive variables.
Moreover, such an extreme point has polynomial encoding length. If its support has size \(t\le r\), select \(t\) linearly independent rows of the corresponding support matrix. The positive variables are the unique solution of a nonsingular \(t\times t\) zero-one system with rational right-hand side. Cramer’s rule and Hadamard’s determinant bound give polynomially many bits in the input length and \(r\).
A certificate therefore lists at most \(r\) bundles and their rational masses. In polynomial time one can:
Hence the problem belongs to \(\mathrm{NP}\).
We reduce from Independent Set. We may assume that the input graph is connected and that \(2\le k\le |V|\). Indeed, instances with \(k<2\) are trivial, and for an arbitrary graph \(G\) with \(k\ge2\), adding one universal vertex produces a connected graph \(G^+\) satisfying
\[ \alpha(G^+)=\max\{\alpha(G),1\}, \]
so \(G^+\) has an independent set of size at least \(k\) exactly when \(G\) does.
Let the connected input graph be
\[ G=(V,E),\qquad V=\{v_1,\ldots,v_n\}. \]
For each \(v_i\), introduce a dummy job type \(d_i\). Define
\[ J=V\mathbin{\dot\cup}\{d_1,\ldots,d_n\}. \]
The conflict graph \(H\) has edge set
\[ F=E\cup\bigl\{\{v_i,d_i\}:1\le i\le n\bigr\}. \]
Thus each dummy \(d_i\) is a pendant neighbour of \(v_i\). Since \(G\) is connected, \(H\) is connected.
There are two employee types: a selector type \(s\) and a filler type \(f\), with masses
\[ \mu_s=1,\qquad \mu_f=n. \]
Every job type has supply
\[ \sigma_x=1\qquad\text{for every }x\in J. \]
Set the common target to
\[ P^\star=n^2+k. \]
For the selector type, set
\[ p_s(v_i)=n+1,\qquad p_s(d_i)=n, \]
and set \(c_s(x)=0\) for every \(x\in J\), with \(B_s=0\).
For the filler type, set
\[ p_f(x)=P^\star,\qquad c_f(x)=1 \]
for every \(x\in J\), with \(B_f=1\). Finally, use \(P=P^\star\) as the target of the constructed instance.
The construction is polynomial, and every numerical value is at most polynomial in \(n\).
Let \(S\subseteq J\) be independent in \(H\). Because \(v_i\) conflicts with \(d_i\), \(S\) contains at most one element from each pair \(\{v_i,d_i\}\). Hence
\[ |S|\le n. \]
Its selector utility is
\[ p_s(S)=n|S|+|S\cap V|. \]
If \(|S|\le n-1\), then
\[ p_s(S)\le (n+1)(n-1)=n^2-1<n^2+k=P^\star. \]
Therefore every eligible selector bundle has \(|S|=n\). It consequently contains exactly one element from every pair \(\{v_i,d_i\}\). Writing \(T=S\cap V\), we then have
\[ p_s(S)=n^2+|T|. \]
Thus \(p_s(S)\ge P^\star\) exactly when \(|T|\ge k\). Since all conflicts among original vertices are precisely the edges of \(G\), \(T\) is independent in \(G\).
Conversely, if \(T\subseteq V\) is independent in \(G\), then
\[ S(T)=T\cup\{d_i:v_i\notin T\} \]
is independent in \(H\), contains exactly one element from every pair, and satisfies
\[ p_s(S(T))=n^2+|T|. \]
Therefore eligible selector bundles correspond exactly to independent sets of \(G\) having size at least \(k\).
For the filler type, a bundle \(R\) is eligible exactly when it is a singleton. Indeed,
\[ c_f(R)=|R|\le1 \]
and
\[ p_f(R)=P^\star|R|\ge P^\star \]
together imply \(|R|=1\).
Suppose first that \(G\) has an independent set \(T\) with \(|T|\ge k\). Assign the entire selector mass to \(S(T)\):
\[ y_{s,S(T)}=1. \]
The bundle \(S(T)\) contains exactly \(n\) of the \(2n\) job types. For every \(x\notin S(T)\), assign one unit of filler mass to the singleton \(\{x\}\):
\[ y_{f,\{x\}}=1. \]
All other variables are zero. There are exactly \(n\) jobs outside \(S(T)\), so the total filler mass is \(n=\mu_f\). Each job type occurs either in the selector bundle or in exactly one filler singleton, and hence receives total mass \(1=\sigma_x\). Every positive-mass bundle is eligible. The constructed instance is feasible.
Conversely, suppose the constructed instance is feasible. Since
\[ \sum_S y_{s,S}=\mu_s=1, \]
there is at least one selector bundle \(S\) with \(y_{s,S}>0\). The eligibility implication forces this bundle to satisfy the selector budget and utility conditions. By the preceding characterization, \(S\cap V\) is an independent set of \(G\) of size at least \(k\). Thus \(G\) is a yes-instance of Independent Set.
The reduction is therefore correct.
The feasibility problem is both in \(\mathrm{NP}\) and \(\mathrm{NP}\)-hard, hence \(\mathrm{NP}\)-complete. Fractional splitting of employee masses does not remove the hardness: every positive-mass selector bundle must itself encode a large independent set, while the filler type absorbs the complementary job supplies.
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes \(\mathrm{NP}\)-membership and gives a substantively valid reduction from Independent Set. The reduction survives fractional splitting because every positive selector bundle individually determines an independent set of size at least \(k\).
There is one minor formal gap in the preprocessing used to restrict Independent Set instances. It is routine but should be stated explicitly.
Restricting variables to eligible pairs \((a,S)\) is equivalent to the original implication: every ineligible bundle must receive mass zero. The matrix description correctly encodes both employee-mass and job-supply equalities.
The boundedness argument is correct: for each variable, \(0\le y_{a,S}\le\mu_a\). Thus a nonempty feasible polytope has an extreme point.
At an extreme point, the columns indexed by positive variables must be linearly independent. Otherwise a sufficiently small perturbation along a dependence vector would preserve the equalities and nonnegativity in both directions, contradicting extremality. Hence at most \(|A|+|J|\) variables are positive.
The encoding-length argument is also valid. A full-column-rank support matrix contains a nonsingular square row submatrix. Cramer’s rule and Hadamard’s bound yield polynomial-size rational coordinates because the matrix is zero-one and the right-hand side has polynomial encoding length.
The proposed certificate contains polynomially many explicitly represented bundles and rational masses. Independence, additive utilities and costs, eligibility, and all equality constraints can be checked exactly in polynomial time. Thus \(\mathrm{NP}\)-membership is established.
Adding a universal vertex correctly produces a connected graph and, for \(k\ge2\), preserves whether an independent set of size at least \(k\) exists.
However, the claimed restriction \(2\le k\le |V|\) is not completely justified as written. Instances with \(k>|V|\) are not discussed, and adding a universal vertex does not necessarily place them inside the stated range. Likewise, degenerate instances with \(k<2\) are called trivial without specifying their images under the many-one reduction. A formal reduction must map these cases to fixed connected yes- or no-instances satisfying the desired range. This is a routine finite-case completion and does not undermine the main construction.
The conflict graph consists of the connected graph \(G\) together with one pendant dummy vertex at each original vertex. It is therefore connected.
There are exactly two employee types. All numerical parameters are nonnegative integers. Under \(k\le n\), their magnitudes are bounded by a polynomial in \(n\).
Every independent bundle contains at most one of \(v_i,d_i\), so its size is at most \(n\). The utility identity
\[ p_s(S)=n|S|+|S\cap V| \]
is correct.
When \(|S|\le n-1\), the bound
\[ p_s(S)\le(n+1)(n-1)=n^2-1<n^2+k \]
is correct. Thus an eligible selector bundle must have size \(n\), hence exactly one element from every pair.
For such a bundle, its original-vertex portion \(T\) is independent in \(G\), and its utility is \(n^2+|T|\). Eligibility is therefore equivalent to \(|T|\ge k\). Conversely, the displayed construction \(S(T)\) is independent and has the stated utility. The correspondence is valid.
The filler budget gives \(|R|\le1\), while the positive target excludes \(R=\varnothing\). Consequently the eligible filler bundles are exactly singletons. This reasoning is correct.
Given a large independent set, the selector consumes exactly one job from each pair, and the \(n\) complementary jobs receive one filler singleton each. Employee masses and all job supplies are satisfied exactly.
Conversely, selector mass \(1\) guarantees at least one positive selector variable. Its bundle must be eligible and therefore yields an independent set of size at least \(k\). Fractional splitting creates no loophole because eligibility applies separately to every positive selector bundle.
The central reduction and the \(\mathrm{NP}\)-membership argument are correct. Only the routine treatment of trivial or out-of-range Independent Set instances is missing. The claimed \(\mathrm{NP}\)-completeness result is therefore established in substance with a minor formal gap.
⟨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.