Answer: \(\mathrm{NP}\)-hard under the specified accuracy dependence; an algorithm polynomial in \(m,\tau,H,L,1/\epsilon\) would imply \(\mathrm P=\mathrm{NP}\).
Theorem 4.1 — class: hardness
Given rational type masses \(\mu_t\), contact rates \(a_{st}\), community memberships \(b_{jt}\), a seed-mass budget \(\kappa\), and a finite horizon \(H\), optimize over \(x_t\in[0,1]\) with \(\sum_t\mu_t x_t\le\kappa\). Define \(z_t^{(0)}=x_t\) and \(z_t^{(h+1)}=1-(1-x_t)\exp(-\sum_s\mu_s a_{st}z_s^{(h)})\); maximize \(F_H(x)=\sum_t\mu_t z_t^{(H)}\) subject to equal coverage \(\phi_j(x)=\sum_t b_{jt}\mu_t z_t^{(H)}/\sum_t b_{jt}\mu_t\) across communities. Determine the complexity, in \(|T|\), \(H\), input bit length, and \(1/\epsilon\), of finding a rational solution with objective within \(\epsilon\) of optimum and parity violations at most \(\epsilon\).
A society is given by its support: a list \(T\) of \(\tau\ge1\) types with positive masses \(\mu_t\) encoded as binary rationals, with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Input also includes nonnegative binary rational contact rates \(a_{st}\), a binary rational budget \(\kappa\in[0,1]\), and a horizon \(H\in\mathbb Z_{\ge0}\) encoded in unary. There are \(m\ge1\) communities, specified by indicators \(b_{jt}\in\{0,1\}\), each with positive mass \(M_j=\sum_t b_{jt}\mu_t\); communities may overlap and need not cover the society.
A seed allocation is \(x\in[0,1]^T\) satisfying \(\sum_t\mu_t x_t\le\kappa\). Define \(z_t^{(0)}=x_t\) and \(z_t^{(h+1)}=1-(1-x_t)\exp(-\sum_s\mu_s a_{st}z_s^{(h)})\) for \(0\le h<H\).
Set \(F_H(x)=\sum_t\mu_t z_t^{(H)}\) and \(\phi_j(x)=M_j^{-1}\sum_t b_{jt}\mu_t z_t^{(H)}\). Let \(\mathrm{OPT}\) be the maximum of \(F_H\) over budget-feasible real allocations satisfying \(\phi_i(x)=\phi_j(x)\) for every pair of communities.
For a binary rational \(\epsilon\in(0,1)\), the computational problem is to find a rational budget-feasible allocation with \(F_H(x)\ge\mathrm{OPT}-\epsilon\) and \(|\phi_i(x)-\phi_j(x)|\le\epsilon\) for all pairs. Guarantees concern the real values of the recurrence; \(L\) denotes the total input bit length, including \(\epsilon\).
Is this approximation problem solvable in time polynomial in \(m,\tau,H,L,1/\epsilon\), or is it NP-hard under this accuracy dependence?
For discrete seed sets under Independent Cascade diffusion, no polynomial-time algorithm achieves any fixed positive multiplicative objective factor while ensuring \(\sigma_{C_i}(S)\ge\beta\sigma_{C_j}(S)\) for all pairs, for any fixed \(\beta\in(0,1]\), unless \(\mathrm P=\mathrm{NP}\); here \(\sigma_C\) is expected community coverage. [Discrete hardness result](https://ojs.aaai.org/index.php/AAAI/article/download/26651/26423).
No result settling the specified mass recurrence and additive-error problem was located in the literature search.
1. Result
The approximation problem is \(\mathrm{NP}\)-hard under the specified accuracy dependence. A deterministic algorithm running in time polynomial in \(m,\tau,H,L,1/\epsilon\) would imply \(\mathrm P=\mathrm{NP}\).
This holds already for \(H=1\), with two distinct, disjoint singleton communities. The proof below uses the given mass recurrence directly.
2. A graph quadratic lemma
Let \(G\) be a simple undirected graph on \(\{1,\ldots,n\}\), and let \(\omega\) be its maximum clique size. Define the symmetric matrix \(B\) by setting \(B_{ij}=1\) when \(i=j\) or when distinct vertices \(i,j\) are nonadjacent, and \(B_{ij}=0\) otherwise.
For every \(v\in\mathbb R_{\ge0}^n\), put \(r=\sum_i v_i\) and \(Q(v)=\sum_{i,j}B_{ij}v_iv_j\). Then
\[ Q(v)\ge \frac{r^2}{\omega}. \]
Equality holds when \(v\) assigns mass \(r/\omega\) to each vertex of a maximum clique and zero elsewhere.
To prove the inequality, the case \(r=0\) is immediate. Otherwise normalize to \(p=v/r\), so \(\sum_i p_i=1\).
Suppose two nonadjacent vertices \(i,j\) both have positive coordinates. Keep all other coordinates fixed and redistribute their total mass \(s=p_i+p_j\). Their contribution involving only these two coordinates is
\[ p_i^2+2p_ip_j+p_j^2=s^2. \]
Their interactions with the remaining coordinates have the form \(2p_i\alpha+2p_j\beta\), where \(\alpha,\beta\) are fixed. Moving all mass \(s\) to the coordinate with the smaller coefficient does not increase \(Q\), and decreases the number of positive coordinates.
Repeating this operation terminates at a vector \(p'\) whose support is a clique, of some size \(\ell\le\omega\). Consequently, by Cauchy–Schwarz,
\[ Q(p)\ge Q(p')=\sum_i(p'_i)^2\ge\frac1\ell\ge\frac1\omega. \]
Multiplication by \(r^2\) proves the claim. The stated equality case follows directly from the definition of \(B\).
3. Construction of the diffusion instance
We reduce from CLIQUE: given \(G\) and an integer \(k\), decide whether \(\omega\ge k\). This problem is \(\mathrm{NP}\)-complete; see [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9). We may restrict to \(n\ge2\) and \(2\le k\le n\), since other cases are directly decidable.
Define
\[ \lambda=\frac1{8n^3}, \qquad \epsilon=\frac{\lambda^2}{2}=\frac1{128n^6}, \qquad c_i=\sum_{j=1}^n B_{ij}. \]
There are \(n+2\) types: the vertex types and two additional types \(d_1,d_2\). Set
\[ \mu_i=\frac1{2n}\quad(1\le i\le n), \qquad \mu_{d_1}=\mu_{d_2}=\frac14, \qquad \kappa=\frac1{2n}. \]
These masses are positive and sum to one. Choose \(H=1\). The two communities are \(C_1=\{d_1\}\) and \(C_2=\{d_2\}\), each of mass \(1/4\).
Set the contact rates to
\[ a_{ij}=2n\lambda B_{ij}\quad(1\le i,j\le n), \qquad a_{i,d_\ell}=2\lambda(n-c_i)\quad(\ell\in\{1,2\}), \]
and set every rate whose source is \(d_1\) or \(d_2\) to zero. Since \(1\le c_i\le n\), all rates are nonnegative binary rationals.
For a budget-feasible allocation \(x\), write
\[ r=\sum_{i=1}^n x_i, \qquad p(x)=\sum_t\mu_tx_t. \]
The budget inequality gives
\[ \frac{r}{2n}+\frac{x_{d_1}+x_{d_2}}4\le\frac1{2n}, \]
and hence \(0\le r\le1\).
Let \(u_t=\sum_s\mu_sa_{st}x_s\) be the exponent argument in the one-round recurrence. Our construction gives
\[ u_j=\lambda\sum_i B_{ij}x_i, \qquad u_{d_1}=u_{d_2}=u_d =\frac{\lambda}{n}\sum_i(n-c_i)x_i. \]
Therefore \(0\le u_t\le\lambda\) for every type.
4. A rational upper bound and the exponential error
Define the rational expression
\[ \mathcal G(x)=p(x)+\sum_t\mu_t(1-x_t)u_t. \]
For every \(u\ge0\),
\[ 0\le u-(1-e^{-u}) =\int_0^u(1-e^{-v})\,dv \le\int_0^u v\,dv =\frac{u^2}{2}. \]
Because \(z_t^{(1)}=x_t+(1-x_t)(1-e^{-u_t})\), the preceding bound implies
\[ 0\le\mathcal G(x)-F_1(x) \le\sum_t\mu_t(1-x_t)\frac{u_t^2}{2} \le\frac{\lambda^2}{2} =\epsilon. \]
We next calculate \(\mathcal G\). The balancing types make the linear influence term independent of the graph degrees:
\[ \sum_t\mu_tu_t =\frac{\lambda}{2n}\sum_i c_ix_i +\frac{\lambda}{2n}\sum_i(n-c_i)x_i =\frac{\lambda r}{2}. \]
The corresponding subtraction term is
\[ \sum_t\mu_tx_tu_t =\frac{\lambda}{2n}Q(x_1,\ldots,x_n) +\frac{x_{d_1}+x_{d_2}}4\,u_d. \]
The last summand is nonnegative. Using the budget and the graph quadratic lemma, we obtain
\[ \mathcal G(x) \le\kappa+\frac{\lambda}{2n}(nr-Q(x_1,\ldots,x_n)) \le\kappa+\frac{\lambda}{2n}\left(nr-\frac{r^2}{\omega}\right). \]
For \(0\le r\le1\),
\[ \left(n-\frac1\omega\right) -\left(nr-\frac{r^2}{\omega}\right) =(1-r)\left(n-\frac{1+r}{\omega}\right)\ge0, \]
because \(n\ge2\) and \(\omega\ge1\).
For \(1\le\ell\le n\), define
\[ A_\ell=\kappa+\frac{\lambda}{2n}\left(n-\frac1\ell\right). \]
Thus every budget-feasible allocation, regardless of its fairness violation, satisfies
\[ F_1(x)\le\mathcal G(x)\le A_\omega. \]
5. An exactly fair clique witness
Let \(S\) be a maximum clique. Choose
\[ x_i=\frac1\omega\quad(i\in S), \qquad x_i=0\quad(i\notin S), \qquad x_{d_1}=x_{d_2}=0. \]
This allocation lies in the unit cube and uses budget exactly \(\kappa\). The two balancing types have identical exponent arguments and identical seed coordinates. Hence
\[ \phi_1(x)=z_{d_1}^{(1)}=1-e^{-u_d} =z_{d_2}^{(1)}=\phi_2(x). \]
The witness therefore satisfies the exact fairness constraint used to define \(\mathrm{OPT}\).
For this allocation, \(r=1\), \(Q=1/\omega\), and \(\mathcal G(x)=A_\omega\). Combining the witness with the universal upper bound proves
\[ A_\omega-\epsilon\le\mathrm{OPT}\le A_\omega. \]
The maximum exists: the exactly fair feasible set is nonempty, closed, and bounded, and \(F_1\) is continuous.
6. Deciding CLIQUE from any valid approximate allocation
Suppose an algorithm supplies the allocation required in the question. Apply it to the constructed instance with accuracy \(\epsilon=\lambda^2/2\), obtaining a rational allocation \(\widehat x\).
If \(\omega\ge k\), the objective guarantee and the exactly fair witness imply
\[ \mathcal G(\widehat x)\ge F_1(\widehat x) \ge\mathrm{OPT}-\epsilon \ge A_k-2\epsilon =A_k-\lambda^2. \]
If \(\omega\le k-1\), the universal upper bound gives
\[ \mathcal G(\widehat x)\le A_\omega\le A_{k-1}. \]
The gap between consecutive thresholds satisfies
\[ A_k-A_{k-1} =\frac{\lambda}{2nk(k-1)} \ge\frac{\lambda}{2n^3} =4\lambda^2. \]
Consequently:
Comparison with the rational threshold \(A_k-2\lambda^2\) therefore decides CLIQUE correctly. Computing \(\mathcal G(\widehat x)\) requires only exact rational arithmetic; no numerical evaluation of an exponential is needed. The argument applies to every output meeting the requested guarantees, including outputs with nonzero permitted fairness error.
The constructed instance has \(m=2\), \(\tau=n+2\), \(H=1\), total bit length \(L=O(n^2\log n)\), and \(1/\epsilon=128n^6\). Thus an algorithm with the proposed polynomial running time, followed by the rational comparison above, would decide CLIQUE in polynomial time. This proves the claimed hardness.
⟨structured verdict parsed — rendered above⟩
The proof resolves the task. Its reduction establishes hardness for the specified continuous recurrence and additive approximation guarantees, already with \(H=1\) and two disjoint singleton communities. I found no major or minor issues.
The matrix \(B\) is symmetric, includes every diagonal entry, and includes both ordered entries for each nonedge. Thus the contribution of two nonadjacent positive coordinates is exactly \((p_i+p_j)^2\).
With their total mass fixed, their remaining interactions are linear in those coordinates. Moving their mass to the coordinate with the smaller coefficient cannot increase \(Q\), preserves nonnegativity and normalization, and strictly decreases support size. The process therefore terminates with nonempty clique support.
Cauchy–Schwarz applies to the resulting \(\ell\) positive coordinates, whose sum is one, giving \(Q(p')\ge 1/\ell\ge 1/\omega\). Normalization and rescaling are valid for \(r>0\); the case \(r=0\) is correctly handled separately. The stated equality witness is also correct.
The cited theorem is precisely the NP-completeness of deciding whether an input graph contains \(k\) mutually adjacent vertices, equivalently whether \(\omega\ge k\). This matches [Karp’s original theorem](https://www.scribd.com/document/953735605/Karp-1972).
Restricting to \(n\ge2\) and \(2\le k\le n\) removes only directly decidable cases. In particular, \(k-1\) is positive wherever \(A_{k-1}\) is used.
There are exactly \(n+2\) positive-mass support types. Their masses sum to one, the budget lies in \([0,1]\), and both communities have positive mass. Disjoint singleton communities are allowed by the task.
The contact rates are nonnegative because \(1\le c_i\le n\). All numerical parameters are rational with polynomial binary encoding length. Also, \(0<\epsilon=1/(128n^6)<1\), and \(H=1\) satisfies the unary horizon requirement.
The source and target indices in the contact rates agree with the recurrence. Substituting the masses gives the displayed formulas for \(u_j\) and \(u_d\). The budget implies \(0\le r\le1\), and consequently every exponent argument satisfies \(0\le u_t\le\lambda\).
The integral identity and the bound \(1-e^{-v}\le v\) give \(0\le u-(1-e^{-u})\le u^2/2\) for every \(u\ge0\).
The weights \(\mu_t(1-x_t)\) are nonnegative and sum to at most one. Therefore the claimed bound \(0\le\mathcal G(x)-F_1(x)\le\lambda^2/2=\epsilon\) is valid. Its direction is used consistently throughout the reduction.
The two balancing types together contribute \(\lambda(2n)^{-1}\sum_i(n-c_i)x_i\) to the linear influence term. This exactly cancels the degree dependence of the vertex contribution, yielding \(\sum_t\mu_tu_t=\lambda r/2\).
The subtraction term has the stated vertex contribution \(\lambda Q(x)/(2n)\). Its balancing-type contribution is nonnegative, so discarding it gives an upper bound.
Applying the budget and quadratic lemma gives \(\mathcal G(x)\le\kappa+\lambda(nr-r^2/\omega)/(2n)\). The displayed factorization comparing this expression with its value at \(r=1\) is correct. Its sign follows from \(1-r\ge0\), \(n\ge2\), and \((1+r)/\omega\le2\).
Thus \(F_1(x)\le\mathcal G(x)\le A_\omega\) holds for every budget-feasible allocation, including allocations that violate exact fairness.
The maximum-clique allocation lies in the unit cube and uses exactly the budget. Equal zero seed coordinates and identical exponent arguments at the singleton community types imply exactly equal normalized community coverage.
For this witness, \(r=1\), \(Q=1/\omega\), and the balancing subtraction vanishes. Hence \(\mathcal G(x)=A_\omega\), and the exponential error bound gives \(F_1(x)\ge A_\omega-\epsilon\).
Combined with the universal upper bound, this establishes \(A_\omega-\epsilon\le\mathrm{OPT}\le A_\omega\). The existence claim is justified: the exactly fair feasible set is nonempty and compact, and the objective and fairness functions are continuous.
In a yes-instance, every valid approximate output satisfies \(\mathcal G(\widehat x)\ge A_k-\lambda^2\). In a no-instance, every budget-feasible output satisfies \(\mathcal G(\widehat x)\le A_{k-1}\).
The threshold difference is exactly \(\lambda/(2nk(k-1))\). Since \(k(k-1)\le n^2\), it is at least \(\lambda/(2n^3)=4\lambda^2\).
Therefore the rational threshold \(A_k-2\lambda^2\) strictly separates the two cases. There is no boundary ambiguity. Permitted fairness error cannot invalidate the reduction because its upper bound applies without any fairness assumption.
The stated encoding bound \(L=O(n^2\log n)\) and accuracy dependence \(1/\epsilon=128n^6\) are polynomial in the graph size.
Under the hypothesized polynomial-time algorithm, the rational output has polynomial encoding length. Evaluating the displayed rational expression \(\mathcal G(\widehat x)\) and comparing it with the rational threshold therefore also take polynomial time. No exponential evaluation or exact fairness test is required.
This proves the claimed polynomial-time implication and the corresponding hardness of the approximation search problem. The proof does not claim NP membership or NP-completeness.
No repair or additional 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.