Answer: Polynomial-time computable; the specified mass recurrence admits a deterministic fully polynomial approximation scheme.
Theorem 3.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any $\eps>0$, the node-based probabilistic maximin problem, cannot be approximated to within a factor $1-1/e+\epsilon$ unless $P=NP$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite seed and recipient type sets \(E\) and \(R\), rational masses \(\mu_t>0\) summing to \(1\), a directed acyclic contact graph with rational rates \(\beta_{st}\), recipient communities \(\mathcal C\), and a rational seed-mass budget \(\kappa\), choose \(x_s\in[0,1]\) with \(\sum_{s\in E}\mu_s x_s\le\kappa\). Set \(r_s=x_s\) for seed types and, in topological order, \(r_t=1-\exp(-\sum_{s:(s,t)\in A}\mu_s\beta_{st}r_s)\) for downstream types. What is the maximum of \(\min_{C\in\mathcal C}\frac{\sum_{t\in C}\mu_t r_t}{\sum_{t\in C}\mu_t}\), or an additive-\(\epsilon\) approximation to it?
A society is given by its support: disjoint nonempty seed and recipient type sets \(E,R\), with \(\tau=|E\cup R|\) positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) counts listed types, not possible types.
The input includes a directed acyclic graph \((E\cup R,A)\) with no arcs entering \(E\), nonnegative binary-rational contact rates \(\beta_{st}\), and an explicitly listed family \(\mathcal C\) of \(m\ge1\) nonempty subsets of \(R\), possibly overlapping.
The binary-rational budget satisfies \(0<\kappa\le\sum_{s\in E}\mu_s\). Feasible allocations satisfy \(x_s\in[0,1]\) and \(\sum_{s\in E}\mu_sx_s\le\kappa\); only seed types can receive allocations.
Set \(r_s=x_s\) for \(s\in E\), and in topological order set \(r_t=1-\exp(-\sum_{s:(s,t)\in A}\mu_s\beta_{st}r_s)\) for \(t\in R\), with an empty sum equal to \(0\).
Define \(F(x)=\min_{C\in\mathcal C}\frac{\sum_{t\in C}\mu_tr_t}{\sum_{t\in C}\mu_t}\) and \(\mathrm{OPT}=\max_xF(x)\). Let \(L\) be the total binary input length, including a rational accuracy parameter \(\epsilon\in(0,1)\); computation uses the Turing bit model.
For each fixed \(\eta\in(0,1/e)\), can a feasible rational allocation satisfying \(F(x)\ge(1-1/e+\eta)\mathrm{OPT}-\epsilon\) be computed in time polynomial in \(m,\tau,L,1/\epsilon\), or is obtaining this guarantee NP-hard?
For finite agents under Independent Cascade diffusion, independent seed selection with an expected cardinality budget has no polynomial-time multiplicative \((1-1/e+\eta)\)-approximation unless \(\mathrm P=\mathrm{NP}\), even on bipartite graphs with one recipient community; a randomized \((1-1/e)\)-approximation with arbitrarily small additive loss is known. [Source](https://arxiv.org/pdf/2010.03438)
No result settling this approximation question for the specified mass recurrence was identified in the literature search.
The requested guarantee is computable in polynomial time. In fact, the specified mass recurrence admits a deterministic fully polynomial approximation scheme: a feasible rational allocation satisfying
\(F(x)\ge (1-\epsilon/2)\mathrm{OPT}\)
can be computed in time polynomial in \(m,\tau,L,1/\epsilon\).
The proof constructs a rational linear program. Its key ingredient is a multiplicative approximation to the scalar response function; this prevents large contact rates from amplifying approximation errors.
Write \(a_{st}=\mu_s\beta_{st}\ge0\), and define
\(h(z)=1-\exp(-z)\qquad(z\ge0).\)
The function \(h\) is increasing and concave, satisfies \(h(0)=0\), and takes values in \([0,1]\). Consequently, for \(c\in[0,1]\),
\(h(cz)\ge c h(z).\)
Indeed, concavity applied to \(cz=c z+(1-c)0\) gives this inequality.
The recurrence also makes every \(r_t(x)\) concave in the seed allocation. Seed responses are affine. Inductively, a nonnegative linear combination of predecessor responses is concave, and composition with the increasing concave function \(h\) preserves concavity. Thus every community average is concave, as is their pointwise minimum \(F\).
The feasible allocation set is nonempty and compact, and \(F\) is continuous. Therefore an optimal allocation \(x^*\) exists. Also,
\(0\le\mathrm{OPT}\le1.\)
Concavity alone does not establish the required bit complexity. The following explicit approximation supplies that part.
Choose the smallest positive integer \(k\) such that
\(d=2^{-k}\le\epsilon/(4\tau),\)
and set
\(T=k,\qquad N=T/d=k2^k,\qquad \lambda=1-2d.\)
Since \(\tau\ge2\) and \(\epsilon<1\), we have \(d<1/8\) and \(0<\lambda<1\). Minimality of \(k\) gives
\(\epsilon/(8\tau)<d\le\epsilon/(4\tau).\)
We will construct a concave piecewise affine function \(\phi\), with rational coefficients, satisfying
\(\lambda h(z)\le\phi(z)\le h(z)\qquad\text{for every }z\ge0.\)
For \(j\in\{1,\ldots,N\}\), put \(q_j=jd\). Define
\(w=\dfrac{d^2}{4(1+2T)}.\)
Compute rational bounds \(\underline e_j,\overline e_j\) satisfying
\(0\le\underline e_j\le\exp(-q_j)\le\overline e_j\le1,\qquad \overline e_j-\underline e_j\le w.\)
A polynomial-time construction of these bounds is given in Section 6.
Set
\(A_j=\overline e_j,\qquad B_j=1-(1+q_j)\underline e_j,\)
and define
\(Q(z)=\min\bigl\{z,\ 1,\ A_jz+B_j:\ 1\le j\le N\bigr\},\qquad \phi(z)=\lambda Q(z).\)
The exact tangent to \(h\) at \(q_j\) is
\(\mathcal T_j(z)=\exp(-q_j)z+1-(1+q_j)\exp(-q_j).\)
Concavity gives \(\mathcal T_j(z)\ge h(z)\). For \(z\ge0\), the enclosure bounds imply
\(A_jz+B_j-\mathcal T_j(z) =(\overline e_j-\exp(-q_j))z +(1+q_j)(\exp(-q_j)-\underline e_j)\ge0.\)
Moreover, \(z\ge h(z)\) and \(1\ge h(z)\). Hence
\(Q(z)\ge h(z),\)
which proves \(\phi(z)\ge\lambda h(z)\).
There are three ranges.
For \(0\le z\le d\): Taylor’s theorem gives
\(h(z)\ge z-z^2/2\ge(1-d/2)z.\)
Since \(Q(z)\le z\) and \(\lambda=1-2d\le1-d/2\),
\(\phi(z)\le\lambda z\le h(z).\)
For \(d\le z\le T\): choose \(q_j=d\lceil z/d\rceil\). Then \(z\le q_j\le T\) and \(q_j-z\le d\). Because \(\lvert h''(u)\rvert=\exp(-u)\le1\) for \(u\ge0\), Taylor’s theorem yields
\(0\le\mathcal T_j(z)-h(z)\le d^2/2.\)
The rational coefficients contribute at most
\(A_jz+B_j-\mathcal T_j(z) \le w(z+1+q_j)\le w(1+2T)=d^2/4.\)
Therefore
\(Q(z)\le h(z)+3d^2/4.\)
Also, \(h(z)\ge h(d)\ge d-d^2/2\ge d/2\). It follows that
\(Q(z)\le(1+3d/2)h(z)\le(1+2d)h(z).\)
Consequently,
\(\phi(z)\le(1-2d)(1+2d)h(z)\le h(z).\)
For \(z\ge T\): since \(e>2\),
\(\exp(-T)=\exp(-k)\le2^{-k}=d.\)
Thus \(h(z)\ge1-d\), whereas
\(\phi(z)\le\lambda=1-2d\le1-d.\)
This completes the proof of
\(\lambda h(z)\le\phi(z)\le h(z)\qquad(z\ge0).\)
In particular, \(\phi(0)=0\) and \(0\le\phi(z)\le1\). All slopes used in \(Q\) are nonnegative, and the minimum of affine functions is concave, so \(\phi\) is increasing and concave.
Introduce variables \(y_t\) for all listed types and a variable \(v\). For each recipient define the linear expression
\(z_t(y)=\sum_{s:(s,t)\in A}a_{st}y_s.\)
For each community write \(M_C=\sum_{t\in C}\mu_t>0\).
Maximize \(v\) subject to:
\(y_t\le\lambda z_t(y)\), \(y_t\le\lambda\), and
\(y_t\le\lambda(A_jz_t(y)+B_j)\) for every \(j\in\{1,\ldots,N\}\).
\(vM_C\le\sum_{t\in C}\mu_t y_t.\)
The recipient constraints are exactly
\(y_t\le\phi(z_t(y)).\)
All constraints have rational coefficients. The zero vector is feasible: indeed, \(B_j\ge0\), because
\((1+q_j)\underline e_j\le(1+q_j)\exp(-q_j)\le1\).
The feasible region is bounded.
Given any feasible LP solution, output \(x_s=y_s\) for \(s\in E\). Its allocation constraints hold exactly.
Let \(r(x)\) be the true recurrence. We prove \(y_t\le r_t(x)\) in topological order. Equality holds for seeds. Assuming the inequality for predecessors, nonnegativity of the coefficients gives
\(z_t(y)\le\sum_{s:(s,t)\in A}a_{st}r_s(x).\)
Using the LP constraints, \(\phi\le h\), and monotonicity of \(h\),
\(y_t\le\phi(z_t(y)) \le h(z_t(y)) \le h\!\left(\sum_{s:(s,t)\in A}a_{st}r_s(x)\right) =r_t(x).\)
The community constraints now imply \(v\le F(x)\). Thus an optimal LP solution produces a feasible allocation whose true value is at least the LP optimum.
Let \(n=|R|\), and list recipients in topological order as \(t_1,\ldots,t_n\). Starting from an optimal true allocation \(x^*\), define
\(\widetilde y_s=x_s^*\qquad(s\in E),\)
and recursively set
\(\widetilde y_{t_i}=\phi\!\left(\sum_{s:(s,t_i)\in A}a_{st_i}\widetilde y_s\right).\)
Together with the minimum community average of \(\widetilde y\) as its value of \(v\), this is an LP-feasible point.
We claim that
\(\widetilde y_{t_i}\ge\lambda^i r_{t_i}(x^*)\qquad(1\le i\le n).\)
Suppose the claim holds for earlier recipients. Every predecessor \(s\) of \(t_i\) satisfies
\(\widetilde y_s\ge\lambda^{i-1}r_s(x^*).\)
For seed predecessors this follows from equality and \(\lambda^{i-1}\le1\). For recipient predecessors \(t_j\), it follows from \(j\le i-1\), the induction hypothesis, and \(\lambda^j\ge\lambda^{i-1}\). Therefore, writing
\(Z_i=\sum_{s:(s,t_i)\in A}a_{st_i}r_s(x^*)\), we obtain
\(\widetilde y_{t_i} \ge\lambda h\!\left(\lambda^{i-1}Z_i\right) \ge\lambda^i h(Z_i) =\lambda^i r_{t_i}(x^*).\)
The first inequality uses \(\phi\ge\lambda h\) and monotonicity; the second uses \(h(cz)\ge c h(z)\). The same argument covers an empty predecessor set, whose sum is zero.
Since \(i\le n\), every recipient satisfies
\(\widetilde y_{t_i}\ge\lambda^n r_{t_i}(x^*)\). Taking community averages and then their minimum shows that the LP optimum is at least
\(\lambda^n\mathrm{OPT}.\)
Consequently, the allocation extracted from an optimal LP solution satisfies
\(F(x)\ge\lambda^n\mathrm{OPT}.\)
Bernoulli’s inequality and the choice of \(d\) give
\(\lambda^n=(1-2d)^n\ge1-2dn \ge1-\epsilon/2,\)
because \(n\le\tau\). This proves the advertised multiplicative guarantee.
First,
\(k=O(\log(\tau/\epsilon)),\qquad N=k2^k<\dfrac{8k\tau}{\epsilon}.\)
Thus the number of affine pieces is polynomial in \(\tau,1/\epsilon\).
Here is an explicit construction of the exponential enclosures. Choose an integer \(p\) satisfying
\(p\ge6T,\qquad 2^{1-p}\le w,\)
with \(p=O(T+\log(1/w))=O(k)\). For each \(q_j\), compute the rational Taylor sum
\(S_j=\sum_{\ell=0}^{p-1}\dfrac{(-q_j)^\ell}{\ell!}.\)
Taylor’s remainder bound gives
\(\lvert S_j-\exp(-q_j)\rvert\le q_j^p/p!.\)
The factorial bound \(p!\ge(p/e)^p\), together with \(q_j\le T\), \(p\ge6T\), and \(e<3\), implies
\(q_j^p/p!\le(eT/p)^p\le2^{-p}.\)
For completeness, the factorial bound follows from
\(\log(p!)\ge\int_1^p\log u\,du\ge p\log p-p\).
Therefore we may take
\(\underline e_j=\max\{0,S_j-2^{-p}\},\qquad \overline e_j=\min\{1,S_j+2^{-p}\}.\)
These enclose the true exponential and have width at most \(2^{1-p}\le w\).
Each \(q_j\) has denominator \(2^k\). A common denominator for its Taylor sum is
\(2^{k(p-1)}(p-1)!\), whose binary length is \(O(kp+p\log p)\). Numerator lengths are polynomial as well: the sum of the absolute Taylor terms is at most \(\exp(q_j)\le\exp(T)\). Hence every enclosure and affine coefficient is computable by rational arithmetic in polynomial time and has polynomial binary length.
The LP has \(\tau+1\) variables and
\(O(\tau(N+1)+m)\) constraints. Expanding their linear expressions gives polynomial total encoding length. Contact rates of large numerical magnitude enter only through the input rational coefficients \(a_{st}\); the approximation grid does not depend on their magnitudes.
We now apply the standard rational linear-programming theorem: a feasible bounded LP with rational data can be optimized exactly, returning a rational optimal solution, in time polynomial in its binary encoding length. This is the polynomial-time linear-programming result initiated by [Khachiyan](https://www.mathnet.ru/eng/dan42319). The hypotheses hold here because the LP is explicitly rational, nonempty, and bounded.
Its seed coordinates therefore give the required rational allocation, with exact budget feasibility, in time polynomial in \(m,\tau,L,1/\epsilon\).
For the stipulated \(\eta\), put \(\alpha=1-1/e+\eta<1\). Since \(\mathrm{OPT}\le1\),
\(F(x)\ge(1-\epsilon/2)\mathrm{OPT} \ge\mathrm{OPT}-\epsilon/2 \ge\alpha\mathrm{OPT}-\epsilon.\)
Thus the requested approximation guarantee is polynomial-time computable.
The [cited Independent Cascade result](https://arxiv.org/pdf/2010.03438) concerns a different response function. For example, with two independently selected seeds and deterministic edges to one recipient, its activation probability is
\(f(x_1,x_2)=1-(1-x_1)(1-x_2).\)
This function is not concave: its values at \((1,0)\) and \((0,1)\) are both \(1\), while its value at their midpoint is \(3/4\). In the specified mass recurrence, the corresponding response is \(h(a_1x_1+a_2x_2)\), which is concave and admits the rational approximation proved above. The Independent Cascade hardness statement therefore does not contradict this algorithm.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned approximation question correctly. The deterministic rational LP construction establishes the stronger guarantee \(F(x)\ge(1-\epsilon/2)\mathrm{OPT}\) in time polynomial in \(m,\tau,L,1/\epsilon\).
No major or minor mathematical issues were found. The report below checks the argument as written; no additional lemmas or repairs are needed.
The stated properties of \(h(z)=1-\exp(-z)\) hold on \(z\ge0\). Its monotonicity, concavity, and value \(h(0)=0\) justify \(h(cz)\ge c h(z)\) for every \(c\in[0,1]\).
The induction establishing concavity of each response is valid: predecessor responses enter with nonnegative coefficients, and composition of a concave function with an increasing concave function preserves concavity. Community averages are concave, and their finite pointwise minimum is concave.
The feasible seed allocation set is nonempty, closed, and bounded. The DAG recurrence defines continuous responses, so the existence of an optimal allocation follows. The bound \(0\le\mathrm{OPT}\le1\) is valid.
Since both type sets are nonempty, \(\tau\ge2\). Consequently, the choice of \(k\) indeed gives \(0<d<1/8\), and hence \(0<\lambda=1-2d<1\).
The minimality calculation
\(\epsilon/(8\tau)<d\le\epsilon/(4\tau)\)
is correct. The grid has exactly \(N=k2^k\) points and ends at \(q_N=T=k\).
These definitions are consistent throughout the proof.
The formula for the exact tangent \(\mathcal T_j\) is correct. Concavity gives \(\mathcal T_j(z)\ge h(z)\).
The displayed difference between the rational affine function and the exact tangent is also correct. Both terms are nonnegative for every \(z\ge0\), using the enclosure inequalities. Thus every affine function used in \(Q\), including \(z\) and \(1\), bounds \(h\) from above.
It follows that \(Q(z)\ge h(z)\) and \(\phi(z)\ge\lambda h(z)\). The direction of these inequalities is correct.
All three ranges are covered, including their shared endpoints.
Thus the global sandwich
\(\lambda h(z)\le\phi(z)\le h(z)\)
is established rigorously. The conclusions about nonnegativity, boundedness, monotonicity, and concavity of \(\phi\) also follow.
The recipient inequalities are exactly the hypograph constraints \(y_t\le\phi(z_t(y))\). Their coefficients are rational.
The zero vector is feasible: the argument proving \(B_j\ge0\) is correct. Explicit coordinate bounds make the feasible region bounded. Every community denominator \(M_C\) is positive because the listed communities are nonempty and the masses are positive.
The topological induction proving \(y_t\le r_t(x)\) is valid. It uses precisely the supplied hypotheses: acyclicity, nonnegative contact coefficients, and \(\phi\le h\). No arcs enter seeds, whose responses equal the extracted allocation coordinates.
The community constraints therefore imply \(v\le F(x)\). Exact LP feasibility gives exact seed budget feasibility.
The recursively defined \(\widetilde y\) is an LP-feasible comparison point. Its coordinates may be real rather than rational; this causes no problem because LP optimality compares against all real feasible points.
The induction
\(\widetilde y_{t_i}\ge\lambda^i r_{t_i}(x^*)\)
is correct. Every recipient predecessor appears earlier in the topological order. Since \(0<\lambda<1\), its induction bound implies the weaker factor \(\lambda^{i-1}\) needed at the current vertex. Seed predecessors satisfy the same bound by equality.
Both subsequent inequalities use previously established properties with valid domains. Empty predecessor sets are explicitly covered.
Positive community weights preserve the common factor \(\lambda^n\), as does taking the minimum. Finally, Bernoulli’s inequality applies and gives
\(\lambda^n\ge1-2dn\ge1-\epsilon/2\).
The constants and dependence on the number of listed types are correct.
The grid size satisfies \(N<8k\tau/\epsilon\), with \(k=O(\log(\tau/\epsilon))\).
The exponential enclosure construction is valid:
The common denominator and numerator estimates establish polynomial binary length. Exact rational arithmetic therefore constructs all coefficients in polynomial time. Expanding the LP introduces only polynomial encoding growth; large contact rates affect coefficient bit lengths rather than the grid size.
The rational LP theorem is stated in the required form: a nonempty bounded rational LP can be optimized exactly in polynomial bit complexity, returning a rational optimizer. This is a standard valid theorem, associated with the cited [polynomial-time linear-programming result](https://www.mathnet.ru/eng/dan42319). All its hypotheses are verified in the output.
For every stipulated \(\eta\), the factor \(\alpha=1-1/e+\eta\) is less than \(1\). The final chain from the stronger multiplicative guarantee to \(F(x)\ge\alpha\mathrm{OPT}-\epsilon\) is correct, including when \(\mathrm{OPT}=0\).
The Independent Cascade example is computed correctly: its two endpoint values are \(1\), while its midpoint value is \(3/4\), violating concavity. The [cited paper](https://arxiv.org/pdf/2010.03438) studies that different probabilistic diffusion model. Its hardness result is not used to justify any step of this algorithm.
No unjustified nontrivial steps, false statements, missing hypotheses, or unresolved edge cases were identified. No clarification or repair 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.