Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 3.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe decision version of FIMAL is Σ𝑝 2-hard even in the deterministic case.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t>0\) summing to \(1\), a partition into communities \(C_j\), baseline block contact rates \(\lambda^0_{tu}\), and budgets \(\kappa,\beta\), choose nonnegative type-pair link rates \(z_{tu}\) with \(\sum_{t,u}\mu_t\mu_u z_{tu}\le\beta\). Seed masses satisfy \(0\le x_t\le\mu_t\) and \(\sum_t x_t\le\kappa\). Let \(r_t^0=x_t/\mu_t\), \(d_t^\ell=r_t^\ell-r_t^{\ell-1}\), and evolve the block-kernel independent-cascade limit by \(r_u^{\ell+1}=r_u^\ell+(1-r_u^\ell)(1-\exp[-\sum_t\mu_t(\lambda^0_{tu}+z_{tu})d_t^\ell])\); write \(R_t(x,z)=\lim_{\ell\to\infty}r_t^\ell\). Define \(X^*(z)\) as the seed-mass vectors maximizing \(\sum_t\mu_tR_t(x,z)\). For fixed additive gap \(\varepsilon>0\), approximate \(\max_z\min_{x\in X^*(z)}\min_j\frac{\sum_{t\in C_j}\mu_tR_t(x,z)}{\sum_{t\in C_j}\mu_t}\), or decide whether this value is at least \(\theta\) using a corresponding rational-input gap formulation.
A society is given by its support \(T\): a list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Let \(C_1,\ldots,C_m\) be a partition of \(T\) into nonempty communities.
Inputs also include finite nonnegative rational directed contact rates \(\lambda^0_{tu}\), rational budgets \(0<\kappa\le1\) and \(\beta\ge0\), and a rational threshold \(\theta\). Let \(L\) be the total binary input length.
Link additions are real rates \(z_{tu}\ge0\) on every ordered type pair, including within-type pairs, subject to \(\sum_{t,u\in T}\mu_t\mu_u z_{tu}\le\beta\). Seed allocations are real vectors in \(\mathcal X=\{x:0\le x_t\le\mu_t,\ \sum_t x_t\le\kappa\}\).
Define the cascade by \(r_t^{-1}=0\), \(r_t^0=x_t/\mu_t\), \(d_t^\ell=r_t^\ell-r_t^{\ell-1}\), and, for \(\ell\ge0\), \(r_u^{\ell+1}=r_u^\ell+(1-r_u^\ell)(1-\exp[-\sum_{t\in T}\mu_t(\lambda^0_{tu}+z_{tu})d_t^\ell])\). Put \(R_t(x,z)=\lim_{\ell\to\infty}r_t^\ell\).
Let \(X^*(z)=\operatorname{argmax}_{x\in\mathcal X}\sum_t\mu_tR_t(x,z)\). Promise that \(X^*(z)\ne\varnothing\) for every feasible \(z\); fairness is evaluated over all exact spread maximizers, without a selected tie-breaking rule.
Define \(V=\sup_{z\text{ feasible}}\inf_{x\in X^*(z)}\min_{1\le j\le m}\frac{\sum_{t\in C_j}\mu_tR_t(x,z)}{\sum_{t\in C_j}\mu_t}\).
Fix a rational constant \(0<\varepsilon<1/2\). The gap decision problem has \(\varepsilon\le\theta\le1-\varepsilon\) and promises either \(V\ge\theta+\varepsilon\) or \(V\le\theta-\varepsilon\).
Is this continuous gap decision problem in \(\mathrm P\), with running time polynomial in \(m,\tau,L\) for fixed \(\varepsilon\), or is it NP-hard?
For finite directed independent-cascade networks, choosing at most \(b\) absent edges to maximize minimum community coverage over all spread-maximizing seed sets of size at most \(k\) has a \(\Sigma_2^p\)-hard decision problem, even with deterministic transmission. [Source](https://ojs.aaai.org/index.php/AAAI/article/view/26652/26424).
No result settling this specified continuous gap problem was located.
The specified gap problem is \(\mathrm{NP}\)-hard for every fixed rational \(\varepsilon\in(0,1/2)\).
The reduction below uses only two communities, equal dyadic masses, and a strictly positive link budget. It verifies the existence promise for every feasible link addition and handles all exact spread maximizers.
The central observation is that sufficiently small contact rates can force every spread-maximizing continuous seed allocation to be integral. Their first-order spread then encodes a weighted directed cut.
Let \(N\ge2\), and let \(W=(W_{tu})\) satisfy:
Choose an integer \(Q\ge1\) such that \(\max_u\sum_tW_{tu}\le Q\), and a real number
\(\displaystyle 0<\delta\le\frac{1}{1000NQ^2}.\)
Let \(U\) be any nonnegative real matrix with
\(\displaystyle \sum_{u,t}U_{ut}\le\frac{\delta}{1000},\)
and define the matrix acting on column vectors by
\(\displaystyle A_{ut}=\delta W_{tu}+U_{ut}.\)
Fix an integer \(k\) with \(1\le k<N\). For seed fractions \(s\in[0,1]^N\) satisfying \(\sum_us_u\le k\), consider the cascade with contact matrix \(A\). Write its limiting vector as \(r(s)\), and its unweighted total spread as \(F(s)=\sum_ur_u(s)\).
Lemma. The following statements hold.
\(\displaystyle C_W(S)=\sum_{t\in S,\ u\notin S}W_{tu}\)
over all sets of cardinality \(k\).
Put \(\rho=\|A\|_\infty\), where the matrix norm is the maximum absolute row sum. Then
\(\displaystyle \rho\le\delta Q+\frac{\delta}{1000}\le2\delta Q\le\frac{2}{1000NQ}<\frac12.\)
Let \(r^0=s\). Multiplying the susceptible-fraction updates through cascade round \(\ell\) gives
\(\displaystyle 1-r_u^{\ell+1}=(1-s_u)\exp\!\left[-(Ar^\ell)_u\right].\)
Indeed, the cumulative increments through that round sum to \(r^\ell\). Thus the cascade iterates the map
\(\displaystyle \Phi_s(r)=1-(1-s)\odot\exp(-Ar),\)
where \(\odot\) and the exponential act coordinatewise.
This map sends \([0,1]^N\) into itself. Its derivative with respect to \(r\) is
\(\displaystyle \operatorname{diag}\!\left((1-s)\odot e^{-Ar}\right)A,\)
whose infinity norm is at most \(\rho<1\). The contraction theorem therefore gives a unique fixed point, and the cascade converges to it.
At this fixed point, define
\(\displaystyle E=\operatorname{diag}(e^{-Ar}),\qquad D=\operatorname{diag}((1-s)\odot e^{-Ar}),\qquad J=DA.\)
Since \(\|J\|_\infty\le\rho<1\), the matrix \(I-J\) is invertible. The implicit function theorem shows that \(r(s)\) is twice continuously differentiable locally, including by local extension at boundary points of the cube. In particular, it is continuous.
The feasible seed polytope is compact, so spread maximizers exist.
Implicit differentiation gives
\(\displaystyle \frac{\partial r}{\partial s}=(I-J)^{-1}E.\)
The inverse equals the entrywise nonnegative series \(\sum_{h\ge0}J^h\), and every diagonal entry of \(E\) is positive. Consequently, \(F\) is strictly increasing in each seed coordinate.
If \(\sum_us_u<k<N\), some coordinate can be increased while remaining feasible, strictly increasing spread. Hence every maximizer satisfies \(\sum_us_u=k\).
We prove that \(F\) is strictly convex along every feasible direction \(v=e_i-e_j\), with \(i\ne j\).
Differentiate along \(s+tv\). Using primes for derivatives with respect to \(t\),
\(\displaystyle r'=(I-J)^{-1}Ev.\)
The bounds \(\|(I-J)^{-1}\|_\infty\le2\) and \(\|E-I\|_\infty\le\rho\) imply
\(\displaystyle \|r'\|_\infty\le2,\qquad \|r'-v\|_\infty\le4\rho.\)
For the second inequality, use
\(\displaystyle r'-v=(I-J)^{-1}\bigl((E-I)v+Jv\bigr).\)
A second differentiation gives
\(\displaystyle r''=(I-J)^{-1}h,\qquad h=-D(Ar')^{\odot2}-2E(v\odot Ar').\)
Set \(h_0=-2v\odot Av\). Then \(\|h_0\|_\infty\le2\rho\). Moreover,
\(\displaystyle \|h-h_0\|_\infty\le4\rho^2+4\rho^2+8\rho^2=16\rho^2.\)
Here the three terms bound, respectively, \(D(Ar')^{\odot2}\), \(2(E-I)(v\odot Ar')\), and \(2v\odot A(r'-v)\). Therefore,
\(\displaystyle \|r''-h_0\|_\infty\le2(16\rho^2+2\rho^2)=36\rho^2.\)
For \(v=e_i-e_j\),
\(\displaystyle \sum_u(h_0)_u=2(A_{ij}+A_{ji}-A_{ii}-A_{jj}).\)
The off-diagonal baseline weights are at least \(1\), while the baseline diagonal vanishes. Thus
\(\displaystyle \sum_u(h_0)_u\ge4\delta-2(U_{ii}+U_{jj})\ge4\delta-\frac{2\delta}{1000}.\)
Combining the bounds yields
\(\displaystyle F''\ge4\delta-\frac{2\delta}{1000}-36N\rho^2 \ge4\delta-\frac{2\delta}{1000}-\frac{144\delta}{1000}>0.\)
Now suppose a maximizer were nonintegral. Since its coordinate sum is the integer \(k\), it would have at least two fractional coordinates. A sufficiently small transfer between those coordinates is feasible in both directions. Strict convexity along that transfer implies that one of the two perturbed allocations has greater spread, a contradiction.
Thus every exact maximizer is integral.
The fixed-point equation gives
\(\displaystyle 0\le r_u-s_u=(1-s_u)\bigl(1-e^{-(Ar)_u}\bigr)\le\rho.\)
This already proves the lemma’s bound on an unseeded coordinate.
For \(0\le a\le\rho\), the exponential remainder satisfies \(|1-e^{-a}-a|\le a^2/2\). Consequently,
\(\displaystyle \left|r_u-s_u-(1-s_u)(As)_u\right|\le\frac32\rho^2.\)
To verify this bound, replacing \(Ar\) by \(As\) costs at most \(\|A(r-s)\|_\infty\le\rho^2\), and the exponential remainder costs at most \(\rho^2/2\).
For an integral seed set \(S\) of size \(k\), it follows that
\(\displaystyle F(\mathbf1_S)=k+\delta C_W(S)+C_U(S)+e_S,\)
where
\(\displaystyle C_U(S)=\sum_{t\in S,\ u\notin S}U_{ut},\qquad 0\le C_U(S)\le\frac{\delta}{1000},\)
and
\(\displaystyle |e_S|\le\frac32N\rho^2\le6N\delta^2Q^2\le\frac{6\delta}{1000}.\)
Every \(C_W(S)\) is a half-integer. Therefore, if \(S\) does not maximize \(C_W\), some set \(S^*\) of size \(k\) satisfies \(C_W(S^*)-C_W(S)\ge1/2\). For these sets,
\(\displaystyle F(\mathbf1_{S^*})-F(\mathbf1_S) \ge\frac{\delta}{2}-\frac{\delta}{1000}-\frac{12\delta}{1000}>0.\)
Every exact spread maximizer therefore maximizes the baseline cut. This completes the lemma.
We reduce from Independent Set: given a simple undirected graph \(G\) on \(n\ge1\) vertices and an integer \(1\le K\le n\), decide whether its independence number \(\alpha(G)\) satisfies \(\alpha(G)\ge K\).
This problem is \(\mathrm{NP}\)-complete. For example, it follows from the classical completeness of Node Cover, since the complement of an independent set is a vertex cover. [Karp’s original completeness results](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Add two vertices \(s\) and \(a\). Let \(H\) retain all edges of \(G\), connect \(a\) to every vertex of \(G\) and to \(s\), and give \(s\) no neighbors in \(G\). Put \(d=n+2\).
Assign vertex rewards
\(\displaystyle \omega_i=1\quad(i\in V(G)\cup\{s\}),\qquad \omega_a=K+\frac12.\)
Set \(M=4(n+1)\). For a binary vector \(b\) on \(V(H)\), define
\(\displaystyle \Psi(b)=\sum_i\omega_i b_i-M\sum_{\{i,j\}\in E(H)}b_ib_j.\)
The total vertex reward is at most \(2n+3/2<M\). Any selected set containing an edge therefore has negative objective, while the empty set has objective zero. Every maximizer of \(\Psi\) is consequently an independent set.
An independent set containing \(a\) can contain no other vertex of \(H\), so its best reward is \(K+1/2\). An independent set excluding \(a\) obtains its best reward by selecting \(s\) and a maximum independent set of \(G\), giving reward \(1+\alpha(G)\).
These rewards differ because one is a half-integer and the other is an integer. Thus:
We next realize this objective through a fixed-cardinality directed cut.
Fix the prescribed constant \(\varepsilon\), and write
\(\displaystyle \gamma=\frac12-\varepsilon>0.\)
Choose the smallest power of two \(N\) satisfying
\(\displaystyle N-1\ge\frac{d+1}{\gamma}.\)
Add \(h=N-d-2\) filler vertices, and two further vertices \(p,q\). The resulting set \(T\) has cardinality \(N\). Let
\(\displaystyle O=V(H)\cup\{\text{filler vertices}\},\qquad k=h+1.\)
The choice of \(N\) implies \(h\ge d\). Give every filler reward zero and extend \(\Psi\) to \(O\), keeping penalties only for edges of \(H\).
Every subset of \(V(H)\) can be extended to exactly \(h\) selected ordinary vertices using fillers: if it selects \(j\le d\) vertices, choose \(h-j\) fillers. Therefore, maximizing \(\Psi\) over exactly \(h\) selected vertices of \(O\) has precisely the distinguished-vertex behavior established above.
For \(i\in O\), let
\(\displaystyle g_i=\frac M2\deg_H(i),\)
taking the degree to be zero for fillers. Put \(D_0=n+2\), and define
\(\displaystyle c_i=g_i-\omega_i+D_0\ge0.\)
Construct a nonnegative directed matrix \(P\) as follows:
Let
\(\displaystyle B_0=1+M|E(H)|+\sum_{i\in O}c_i,\)
and additionally set \(P_{pq}=B_0\). All other entries of \(P\) are zero.
Finally, define
\(\displaystyle W_{tt}=0,\qquad W_{tu}=1+P_{tu}\quad(t\ne u).\)
These weights satisfy all the structural hypotheses of the small-contact lemma.
For any seed set \(S\) of cardinality \(k\), the uniform off-diagonal part contributes exactly \(k(N-k)\). Thus maximizing \(C_W\) is equivalent to maximizing the cut contribution \(C_P\).
If \(p\notin S\) or \(q\in S\), the edge \(p\to q\) contributes nothing. All remaining entries of \(P\) have total weight \(B_0-1\), so \(C_P(S)\le B_0-1\).
There exists a set of cardinality \(k\) containing \(p\) and excluding \(q\), for example \(p\) together with all \(h\) fillers. Every such set earns at least \(B_0\) from \(p\to q\).
Therefore, every maximum cut has \(p\in S\) and \(q\notin S\).
Under those forced choices, exactly \(h\) ordinary vertices are selected. Let their indicators be \(b_i\). Expanding their cut contribution gives
\(\displaystyle C_P(S)=B_0+\sum_{i\in O}c_i(1-b_i) +\frac M2\sum_{\{i,j\}\in E(H)} \bigl(b_i(1-b_j)+b_j(1-b_i)\bigr). \)
Collecting linear and quadratic terms,
\(\displaystyle C_P(S)=B_0+\sum_{i\in O}c_i +\sum_{i\in O}(g_i-c_i)b_i -M\sum_{\{i,j\}\in E(H)}b_ib_j. \)
Since \(g_i-c_i=\omega_i-D_0\) and \(\sum_i b_i=h\),
\(\displaystyle C_P(S)=B_0+\sum_{i\in O}c_i-D_0h+\Psi(b).\)
The terms preceding \(\Psi(b)\) are constant. Hence every maximum directed cut selects \(s\) exactly in the Independent Set YES case:
\(\displaystyle \alpha(G)\ge K\ \Longrightarrow\ s\in S \quad\text{for every maximum cut}, \)
\(\displaystyle \alpha(G)\le K-1\ \Longrightarrow\ s\notin S \quad\text{for every maximum cut}. \)
All entries of \(W\) are half-integers, as required by the lemma.
Give every type equal mass \(\mu_t=1/N\). Since \(N\) is a power of two, these masses are dyadic.
Choose
\(\displaystyle Q=\left\lceil\max_u\sum_tW_{tu}\right\rceil,\qquad \delta=\frac{\gamma}{1000NQ^2}.\)
Set the baseline rates, budgets, and threshold to
\(\displaystyle \lambda^0_{tu}=N\delta W_{tu},\qquad \kappa=\frac{k}{N},\qquad \beta=\frac{\delta}{1000N},\qquad \theta=\frac12. \)
In particular, \(\beta>0\). The communities are
\(\displaystyle C_1=\{s\},\qquad C_2=T\setminus\{s\}.\)
For any feasible real link addition \(z\),
\(\displaystyle \frac1{N^2}\sum_{t,u}z_{tu}\le\beta.\)
Define \(U_{ut}=z_{tu}/N\). Then
\(\displaystyle \sum_{u,t}U_{ut}\le N\beta=\frac{\delta}{1000}.\)
The cascade’s contact matrix is exactly
\(\displaystyle A_{ut}=\mu_t(\lambda^0_{tu}+z_{tu}) =\delta W_{tu}+U_{ut}. \)
Also, writing \(s_t=x_t/\mu_t=Nx_t\), seed feasibility becomes
\(\displaystyle 0\le s_t\le1,\qquad \sum_t s_t\le k.\)
Maximizing weighted spread is equivalent to maximizing \(F(s)\), because weighted spread equals \(F(s)/N\).
The small-contact lemma applies for every feasible real \(z\). Consequently:
Thus every exact spread maximizer has the distinguished seed status established in Section 3, independently of the chosen feasible link addition.
Suppose \(\alpha(G)\ge K\). Every exact spread maximizer seeds \(s\), so \(R_s(x,z)=1\).
It seeds \(k-1=h\) other types. Since cascade adoption never decreases below seeding, the coverage of the second community is at least
\(\displaystyle \frac{h}{N-1} =1-\frac{d+1}{N-1} \ge1-\gamma =\frac12+\varepsilon. \)
Therefore, for every feasible \(z\) and every \(x\in X^*(z)\), minimum community coverage is at least \(\theta+\varepsilon\). Taking the prescribed infimum and supremum gives
\(\displaystyle V\ge\theta+\varepsilon.\)
Suppose \(\alpha(G)\le K-1\). Every exact spread maximizer leaves \(s\) unseeded.
The lemma bounds its eventual coverage by
\(\displaystyle R_s(x,z)\le2\delta Q =\frac{2\gamma}{1000NQ} \le\gamma =\frac12-\varepsilon. \)
Minimum community coverage is at most the coverage of \(C_1=\{s\}\). Hence, for every feasible \(z\) and every exact spread maximizer,
\(\displaystyle \min_j\operatorname{coverage}(C_j)\le\theta-\varepsilon.\)
It follows that
\(\displaystyle V\le\theta-\varepsilon.\)
Both types of output instance therefore satisfy the required gap promise.
For fixed \(\varepsilon\), the quantity \(\gamma\) is a positive constant, and the chosen power of two satisfies
\(\displaystyle N<2\left(1+\frac{d+1}{\gamma}\right).\)
Thus \(N\) is linear in \(n\), with a constant depending only on \(\varepsilon\). The rewards, penalties, directed weights, and \(Q\) have magnitudes bounded by polynomials in \(n\). All constructed rational numbers have polynomial binary encoding length, and the full list of \(N^2\) contact rates can be produced in polynomial time.
The construction has two nonempty communities, finite nonnegative rational baseline rates, positive dyadic masses summing to one, a valid positive seed budget, a strictly positive rational link budget, and an admissible threshold \(\theta=1/2\). The existence promise holds for every feasible link addition.
The reduction maps Independent Set YES instances to \(V\ge\theta+\varepsilon\), and NO instances to \(V\le\theta-\varepsilon\). Therefore the specified continuous gap decision problem is \(\mathrm{NP}\)-hard. A running time polynomial in \(m,\tau,L\), for fixed \(\varepsilon\), would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The claimed reduction is correct. The output establishes \(\mathrm{NP}\)-hardness for every fixed rational \(\varepsilon\in(0,1/2)\), including the existence promise and fairness over all exact spread maximizers. I found no major or minor mathematical issues.
The matrix orientation is consistent: \(A_{ut}\) represents the contribution from source \(t\) to recipient \(u\). Thus the assumption \(\max_u\sum_tW_{tu}\le Q\) bounds the required row norm.
The estimate
\(\rho\le\delta Q+\delta/1000\le2\delta Q<1/2\)
follows from \(Q\ge1\), \(N\ge2\), and the specified bound on \(\delta\).
Multiplying the susceptible-fraction updates correctly yields
\(1-r_u^{\ell+1}=(1-s_u)\exp(-(Ar^\ell)_u)\).
The increments telescope to \(r^\ell\), including the initial increment \(d^0=s\). Hence the original cascade does iterate the stated map \(\Phi_s\).
The contraction argument has its required hypotheses: the cube is complete in the infinity norm, the map preserves the cube, and its derivative has norm at most \(\rho<1\). This establishes a unique fixed point in the cube and convergence of the cascade.
The implicit-function argument also applies. The defining equation is smooth, and its derivative with respect to \(r\) is \(I-J\), which is invertible. Local extension at boundary seed allocations is legitimate. Continuity and compactness therefore establish existence of spread maximizers.
The derivative formula
\(\partial r/\partial s=(I-J)^{-1}E\)
is correct.
Since \(J\) is entrywise nonnegative and has norm below one, its inverse series is entrywise nonnegative. The positive diagonal of \(E\) makes the derivative of total spread strictly positive in every seed coordinate.
If the budget is not exhausted, some coordinate can be increased feasibly because \(k<N\). Therefore every maximizer has coordinate sum exactly \(k\).
Both directional differentiation formulas are correct, including
\(h=-D(Ar')^{\odot2}-2E(v\odot Ar')\).
The bounds
\(\|r'\|_\infty\le2\) and \(\|r'-v\|_\infty\le4\rho\)
follow from the stated inverse and exponential bounds. The three contributions to \(\|h-h_0\|_\infty\) are bounded correctly by \(4\rho^2\), \(4\rho^2\), and \(8\rho^2\). Consequently,
\(\|r''-h_0\|_\infty\le36\rho^2\)
is valid.
For \(v=e_i-e_j\), the sum of the coordinates of \(h_0\) is correctly computed as
\(2(A_{ij}+A_{ji}-A_{ii}-A_{jj})\).
The baseline contributes at least \(4\delta\), and the possible diagonal additions reduce this by at most \(2\delta/1000\).
The error bound satisfies
\(36N\rho^2\le144N\delta^2Q^2\le144\delta/1000\).
Thus the asserted strict positivity of \(F''\) holds uniformly along feasible transfer segments.
A nonintegral allocation whose coordinate sum is the integer \(k\) must have at least two fractional coordinates. The feasible transfer argument therefore applies and excludes every nonintegral maximizer. This establishes integrality of all exact maximizers.
The fixed-point equation gives \(0\le r_u-s_u\le\rho\). In particular, an unseeded coordinate has adoption at most \(2\delta Q\).
The exponential remainder bound is used within its stated range. Replacing \(Ar\) by \(As\) costs at most \(\rho^2\), and the exponential remainder costs at most \(\rho^2/2\). The resulting expansion for integral seed sets is correct.
The aggregate error bound
\(|e_S|\le6N\delta^2Q^2\le6\delta/1000\)
and the addition bound \(0\le C_U(S)\le\delta/1000\) are valid.
Since cut values are half-integers, a strictly suboptimal baseline cut loses at least \(1/2\). The comparison
\(\delta/2-\delta/1000-12\delta/1000>0\)
correctly excludes such a set from being an exact spread maximizer. Only the stated implication is needed; the proof does not require every maximum baseline cut to maximize the continuous spread.
Independent Set is an appropriate NP-complete source problem. Its relationship to Node Cover and the cited completeness result are standard. [Karp’s cited paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
The reward bound \(2n+3/2<M\) is correct for \(1\le K\le n\). Any selection containing an edge has negative objective, whereas the empty selection has objective zero. Hence every maximizer of \(\Psi\) is independent.
The two competing optimum rewards are correctly identified as \(K+1/2\) and \(1+\alpha(G)\). They differ strictly in both cases:
The construction therefore handles ties among maximum independent sets without requiring a tie-breaking rule.
The choice of \(N\), together with \(\gamma<1/2\), supplies enough fillers for \(h\ge d\). Every subset of \(V(H)\) can consequently be extended to exactly \(h\) ordinary selections. The cardinality constraint does not alter the optimum value or distinguished-vertex behavior of \(\Psi\).
All \(c_i\) are nonnegative. In particular, \(D_0=n+2\) exceeds every vertex reward, and \(g_i\ge0\). All constructed weights are half-integers.
The uniform off-diagonal weights contribute exactly \(k(N-k)\). The total weight of all entries of \(P\) other than \(P_{pq}\) is correctly counted as \(B_0-1\). A cut failing either required choice for \(p,q\) therefore has value at most \(B_0-1\), while a feasible cut containing \(p\) and excluding \(q\) receives at least \(B_0\).
Under these forced choices, the cut expansion is correct. The term \(-D_0\sum_i b_i=-D_0h\) is constant, leaving precisely \(\Psi(b)\) as the variable part. Thus every maximum cut has the claimed status of \(s\).
The masses \(1/N\) are positive dyadic rationals summing to one. The contact rates and budgets have the required signs and domains.
The link-budget conversion is correct:
\(\sum_{u,t}U_{ut}\le N\beta=\delta/1000\).
The cascade matrix is exactly \(\delta W_{tu}+U_{ut}\), with the stated orientation.
The substitution \(s_t=Nx_t\) transforms the seed constraints into those of the lemma. Weighted spread equals \(F(s)/N\), so it has exactly the same maximizers.
Because \(\gamma<1/2\), the chosen \(\delta\) satisfies the lemma’s upper bound. The lemma therefore applies to every feasible real addition, including within-type additions. This verifies the existence promise and preserves the distinguished seed status for every exact spread maximizer.
In a YES instance, every exact maximizer fully seeds \(s\) and \(h\) other types. The second-community lower bound is correctly computed:
\(h/(N-1)=1-(d+1)/(N-1)\ge1-\gamma=1/2+\varepsilon\).
Both communities therefore meet the upper promise uniformly over all feasible additions and all maximizers.
In a NO instance, every exact maximizer leaves \(s\) unseeded. Its adoption satisfies
\(R_s\le2\delta Q=2\gamma/(1000NQ)\le\gamma=1/2-\varepsilon\).
The singleton community consequently bounds minimum coverage from above, again uniformly over additions and maximizers.
These uniform statements justify the prescribed infimum and supremum directly. Neither attainment of the outer supremum nor selected tie-breaking is needed.
For fixed \(\varepsilon\), the stated bound on the smallest admissible power of two makes \(N\) linear in \(n\). The weights, \(Q\), and rational parameters have polynomial encoding length, and the full contact-rate matrix can be constructed in polynomial time.
The seed budget satisfies \(0<k/N<1\); both communities are nonempty; \(\beta>0\); and \(\theta=1/2\) satisfies the required threshold restriction.
The reduction maps both source outcomes into the respective promised regions. It establishes the claimed NP-hardness. It does not claim membership in NP, which is unnecessary for this conclusion.
No repair or additional clarification is required.
⟨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.