Answer: NP-hard to approximate within \(Q^{1-\varepsilon}\) for every fixed \(\varepsilon\in(0,1)\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateConsider the InfMax problem (G, F, D, k).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rooted binary hierarchy with τ leaf types, binary-rational masses μ_t summing to \(1\), rational hierarchy weights λ, a population scale \(Q\), a seed-mass budget κ, and a target spread ρ, decide whether there are seed masses \(s_t\in[0,μ_t]\) with \(\sum_t s_t\leκ\) such that the threshold-one cascade reaches terminal mass at least ρ.
A society is given by its support: a list of \(\tau\) leaf types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
The hierarchy is a rooted full binary tree with \(m\) nodes and these leaves. Every node \(v\) has a nonnegative rational weight \(\lambda_v\), with \(\lambda_u\le\lambda_v\) whenever \(u\) is an ancestor of \(v\). Define \(w_{tu}=\lambda_{\operatorname{lca}(t,u)}\), including \(w_{tt}=\lambda_t\); influence is bidirectional.
Inputs also include a binary-encoded integer population scale \(Q\ge1\), a rational budget \(0<\kappa\le1\), and a rational target \(\rho\in[0,1]\). Let \(L\) be the total input bit length.
Seeds are divisible masses \(s_t\in[0,\mu_t]\) with \(\sum_t s_t\le\kappa\). Starting with \(x_t^{(0)}=s_t\), update synchronously and irreversibly: \(x_t^{(r+1)}=\mu_t\) if \(Q\sum_u w_{tu}x_u^{(r)}\ge1\), and otherwise \(x_t^{(r+1)}=x_t^{(r)}\). Within-type infected mass contributes; an individual point has zero mass.
Let \(\sigma(s)=\sum_t x_t^{(\infty)}\), including seeds. The spread decision asks whether \(\sigma(s)\ge\rho\) is feasible; its optimization counterpart has value \(\mathrm{OPT}=\max_s\sigma(s)\).
For each fixed \(\varepsilon\in(0,1)\), does maximizing terminal spread admit a \(Q^{1-\varepsilon}\)-factor approximation in time polynomial in \(m,\tau,L\), or is achieving this factor NP-hard?
For finite populations of \(N\) agents, bidirectional hierarchical influence with additive weights and deterministic unit thresholds is NP-hard to approximate within \(N^{1-\varepsilon}\) for every fixed \(\varepsilon\in(0,1)\). [Verified source](https://arxiv.org/pdf/1710.02827v2)
No result settling this approximation question for the defined divisible-mass model was identified in the literature search.
For every fixed \(\varepsilon\in(0,1)\), achieving a \(Q^{1-\varepsilon}\)-factor approximation is NP-hard for the defined divisible-mass model.
Here an approximation algorithm must return feasible seeds \(s\) satisfying \(\sigma(s)\ge \mathrm{OPT}/Q^{1-\varepsilon}\). The reduction below permits arbitrary fractional seeds. All masses in the constructed instances are dyadic rationals, and all node weights belong to \([0,1]\).
The comb hierarchy is inspired by the [finite-population construction of Schoenebeck and Tao](https://arxiv.org/pdf/1710.02827v2). The proof below supplies a separate soundness argument for divisible seeds.
Start with a Vertex Cover instance consisting of a simple graph on \(n\) vertices, edges \(e_1,\ldots,e_p\), and budget \(k\). We restrict to \(n\ge 2\), \(p\ge 1\), and \(1\le k<n\). Vertex Cover remains NP-hard under these restrictions: the excluded cases are decidable directly.
Define
\[ K=n+k,\qquad A=n(p+2),\qquad R=A+K+10. \]
Choose \(W\) to be the smallest power of two satisfying \(W\ge 1024K^3R\), and define
\[ D=\frac{1}{64K^2R},\qquad \delta=\frac{D}{W},\qquad d=\frac{7\delta}{4},\qquad B=AW+K. \]
For the fixed \(\varepsilon\), choose a fixed integer \(r\ge 1/\varepsilon\). Let \(T\) be the smallest power of two satisfying \(T\ge (4B)^r\), and put
\[ M=T-AW. \]
The constructed instance will have population scale \(Q=T\), budget \(\kappa=K/T\), \(A\) small types of mass \(W/T\), and one reservoir type of mass \(M/T\).
It is convenient to prove the cascade statements in auxiliary units: write \(y_t=Ts_t\) for seeds and \(z_t^{(q)}=Tx_t^{(q)}\) for infected mass. Then the seed budget is \(\sum_t y_t\le K\), capacities are \(W\) or \(M\), and the activation condition is exactly
\[ \sum_u w_{tu}z_u^{(q)}\ge 1. \]
This is precisely the specified model after normalization; the auxiliary units impose no integrality restriction on seeds.
Two useful inequalities are
\[ \frac{K}{W}\le \frac{D}{16} \]
and, with \(\eta=dB+K/W\),
\[ \eta =\frac{7D}{4}\left(A+\frac{K}{W}\right)+\frac{K}{W} <\frac{7}{256K^2}+\frac{1}{1024K^2} =\frac{29}{1024K^2} <\frac{1}{K+1}. \]
Here we used \(W\ge1\), \(R>A+K\), and \(K/W\le D/16<1/(1024K^2)\). In particular, \(\eta<1\).
For each graph vertex \(i\), create types \(C_i,D_i\), and gate types \(G_{i1},\ldots,G_{ip}\), each of capacity \(W\) in auxiliary units. Create one reservoir type \(Z\), of capacity \(M\).
For each \(i,j\), define
\[ c_{ij}= \begin{cases} \frac12,&\text{if }i\text{ is incident to }e_j,\\ \frac54,&\text{otherwise}, \end{cases} \qquad a_{ij}= \frac{1-D((n-1)j+k+c_{ij})}{jW}. \]
Also define
\[ b=\frac{1-D((n-1)(p+1)+k)}{(p+1)W}. \]
Construct the hierarchy as follows.
Thus different arms interact with weight \(\delta\); \(D_i\) interacts with the rest of its own arm with weight \(d\). Gate \(G_{ij}\) interacts with \(C_i\) and every earlier gate in its arm with weight \(a_{ij}\). Reservoir \(Z\) interacts with every type in its own comb with weight \(b\).
We verify the required monotonicity of node weights. All numerators defining \(a_{ij}\) and \(b\) exceed \(1/2\), because their coefficients of \(D\) are smaller than \(R\) and \(DR=1/(64K^2)\). Consequently,
\[ a_{ij}W\ge \frac{1}{2p}>D, \qquad bW\ge \frac{1}{2(p+1)}>D. \]
Moreover,
\[ a_{ij}-a_{i,j+1} = \frac{1-D(k+(j+1)c_{ij}-jc_{i,j+1})}{j(j+1)W}>0. \]
The coefficient of \(D\) in this numerator is at most \(k+3j/4+5/4<R\). Similarly,
\[ a_{ip}-b= \frac{1-D(k+(p+1)c_{ip})}{p(p+1)W}>0, \]
because \(k+(p+1)c_{ip}<R\). Finally, \(dW=7D/4<1/(2(p+1))\), so \(b>d>\delta\). Therefore,
\[ 1\ge a_{i1}>\cdots>a_{ip}>b>d>\delta>0. \]
All ancestor-weight constraints hold.
We will repeatedly use another consequence: every influence weight into a gate or into \(Z\) is at most \(1/W\). Thus all seed mass in types that have not become saturated contributes at most \(K/W\) to any such target.
Suppose the graph has a vertex cover of size at most \(k\). Pad it to a set \(S\) of size exactly \(k\), which is possible since \(k<n\).
Seed one auxiliary unit in each \(C_i\), and one in each \(D_i\) with \(i\in S\). This uses exactly \(K\) units. Since these types have diagonal weight \(1\), they all become saturated in the first update.
Assume inductively that every gate in levels below \(j\) is saturated. Ignoring any additional infections, the influence on \(G_{ij}\) is
\[ a_{ij}jW+\delta((n-1)j+k)W +(d-\delta)W\,\mathbf 1_{\{i\in S\}} = 1-c_{ij}D+\frac34D\,\mathbf 1_{\{i\in S\}}. \]
Because \(S\) covers \(e_j\), at least one endpoint \(i\) belongs to \(S\). Its gate receives influence \(1+D/4\) and activates.
The other endpoint gate then receives an additional \(\delta W=D\). Even if its endpoint is outside \(S\), its influence is at least \(1-D/2+D>1\), so it activates too.
A nonendpoint gate whose vertex belongs to \(S\) activates after the first endpoint gate: its influence is at least \(1-5D/4+3D/4+D>1\). A nonendpoint gate outside \(S\) activates after both endpoint gates: its influence is at least \(1-5D/4+2D>1\).
Hence every gate in level \(j\) becomes saturated. Induction proves saturation of all gates.
The reservoir then receives influence
\[ b(p+1)W+\delta((n-1)(p+1)+k)W +(d-\delta)W\,\mathbf 1_{\{1\in S\}} = 1+\frac34D\,\mathbf 1_{\{1\in S\}}\ge1. \]
Therefore \(Z\) activates, and terminal spread is at least \(M/T\).
Now suppose there is no vertex cover of size at most \(k\). Fix any feasible real seed vector in auxiliary units, with total at most \(K\). We prove that \(Z\) never activates.
Call a type saturated when its infected mass equals its capacity. Since \(W>K\) and \(M>K\), no type is saturated initially.
Before \(Z\) activates, no gate in arm \(i\) can saturate before \(C_i\).
Indeed, consider the first gate activation in that arm while \(C_i\) is still unsaturated. All saturated sources outside its comb have influence weight at most \(d\), and their total mass is at most \(AW\). All unsaturated sources together contribute at most \(K/W\). Thus its influence is at most
\[ dAW+\frac{K}{W}\le\eta<1, \]
a contradiction. This also excludes simultaneous first activation of \(C_i\) and a gate: their thresholds are evaluated on the preceding state.
When \(C_i\) first saturates, its own gates are consequently still unsaturated. Its influence is at most \(y_{C_i}+dB+K/W\), so
\[ y_{C_i}\ge 1-\eta. \]
For \(D_i\), every off-diagonal influence weight is at most \(d\). Its first saturation therefore implies \(y_{D_i}\ge1-dB\ge1-\eta\).
If \(K+1\) types among the \(C_i,D_i\) saturated before the reservoir, their seeds would total at least
\[ (K+1)(1-\eta)>K. \]
Therefore at most \(K\) such types can saturate before \(Z\).
Suppose, for contradiction, that \(Z\) first activates in some update. Examine the state immediately before that update.
If \(C_1\) is unsaturated, all gates in arm \(1\) are unsaturated by the preceding argument. Reservoir influence is then at most \(dAW+K/W\le\eta<1\). Hence \(C_1\) must already be saturated.
Let \(h\) be the number of unsaturated \(C_i\) among the other arms. Their gates are also unsaturated. Since at most \(K\) clique types saturate, at most \(k+h\) types \(D_i\) are saturated.
An upper bound on reservoir influence is consequently
\[ b(p+1)W +\delta\big((n-1-h)(p+1)+k+h\big)W +\frac34D+\frac{K}{W} = 1-hpD+\frac34D+\frac{K}{W}. \]
The extra \(3D/4\) allows for saturated \(D_1\). If \(h\ge1\), this is at most
\[ 1-\frac14D+\frac{K}{W}<1. \]
Thus every \(C_i\) is saturated, and at most \(k\) types \(D_i\) are saturated.
If any gate outside arm \(1\) is unsaturated, the reservoir loses at least \(\delta W=D\) relative to the upper bound with all gates saturated. Its influence is at most \(1-D+3D/4+K/W<1\).
If any gate inside arm \(1\) is unsaturated, the corresponding loss is \(bW>D\). Its influence is then at most \(1-bW+3D/4+K/W<1\).
Therefore reservoir activation requires all \(C_i\) and all gates to be saturated beforehand.
Let \(S\) be the graph vertices whose \(D_i\) are saturated immediately before the proposed reservoir activation. We have \(|S|\le k\). Since the Vertex Cover instance is a NO instance, choose an edge \(e_j\) with neither endpoint in \(S\).
We prove by induction over updates, up to the proposed reservoir activation, that no gate in levels \(j,\ldots,p\) saturates.
The statement holds initially. Assume it holds in the current state. Every saturated \(D_i\) in this state belongs to \(S\).
For \(G_{ij}\), upper-bound influence by saturating every \(C_i\), every gate in levels below \(j\), and allowing \(k\) saturated \(D_i\) in the baseline cross-arm contribution. Its influence is at most
\[ 1-c_{ij}D+\frac34D\,\mathbf 1_{\{i\in S\}}+\frac{K}{W}. \]
If \(i\) is an endpoint of \(e_j\), then \(i\notin S\) and \(c_{ij}=1/2\). If \(i\) is a nonendpoint, then \(c_{ij}=5/4\), and its possible bonus is at most \(3D/4\). In both cases the upper bound is at most \(1-D/2+K/W<1\).
Next consider \(G_{i\ell}\) with \(\ell>j\). The analogous baseline assumes all levels below \(\ell\) saturated. But its own preceding gate \(G_{i,\ell-1}\) is unsaturated by the induction hypothesis. Removing that fictitious saturated source reduces influence by \(a_{i\ell}W\). Unsaturated seeds remain covered by the \(K/W\) allowance. Therefore influence is at most
\[ 1-c_{i\ell}D+\frac34D-a_{i\ell}W+\frac{K}{W} \le 1+\frac14D-a_{i\ell}W+\frac{K}{W}<1, \]
using \(a_{i\ell}W>D\) and \(K/W\le D/16\).
No gate in these levels activates in the next update, completing the induction. This contradicts the necessity that all gates saturate before \(Z\).
Thus the reservoir never activates for any feasible fractional seed vector.
The nonreservoir types have total capacity \(AW\), while the reservoir retains at most its seeded mass \(K\). Hence every NO instance satisfies
\[ \mathrm{OPT}\le \frac{AW+K}{T}=\frac{B}{T}. \]
In a YES instance,
\[ \mathrm{OPT}\ge\frac{M}{T} =1-\frac{AW}{T}\ge\frac34, \]
because \(T\ge4B\). In a NO instance, \(\mathrm{OPT}\le B/T\).
Moreover, \(T^\varepsilon\ge4B\), since \(T\ge(4B)^r\) and \(r\varepsilon\ge1\). A \(Q^{1-\varepsilon}\)-approximation, with \(Q=T\), would therefore return in a YES instance spread at least
\[ \frac{3}{4T^{1-\varepsilon}} = \frac{3T^\varepsilon}{4T} \ge\frac{3B}{T} >\frac{B}{T}. \]
This distinguishes YES from NO instances.
The construction meets all encoding requirements:
There are only \(A+1\) types: \(W\) and \(M\) represent auxiliary masses, not explicitly listed individuals.
Finally, spread for rational output seeds is evaluable in polynomial time. Each changing update saturates at least one additional type; thus the process stabilizes after at most \(\tau\) changing updates. Rational arithmetic has polynomial bit complexity.
Consequently, a polynomial-time algorithm achieving the requested approximation would decide Vertex Cover in polynomial time. This proves the claimed NP-hardness for the divisible-mass model.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct. It establishes the claimed approximation hardness for the divisible-mass model, including arbitrary fractional seeds. I found no major or minor mathematical gaps.
The restricted Vertex Cover instances remain NP-hard: the excluded cases are directly decidable, and the remaining instances satisfy the hypotheses used throughout the construction.
The change of units is exact. With \(Q=T\) and \(z_u=Tx_u\), the original activation condition becomes \(\sum_u w_{tu}z_u\ge1\). Likewise, the normalized budget becomes \(\sum_t y_t\le K\). This transformation does not impose integrality on seeds.
The parameter bounds are correct:
The construction also has \(W>K\). Since \(T\ge4B\), it has \(M=T-AW\ge3AW+4K>K\). Thus no feasible seed vector initially saturates any type, as required in the soundness argument.
The hierarchy is a full binary tree with exactly \(A+1\) leaves. Inserting the reservoir inside arm \(1\), below its root of weight \(d\), preserves the stated interaction weights.
The weight calculations check out:
Consequently, weights increase from ancestors to descendants, including at the reservoir insertion. All weights lie in \([0,1]\).
The bound on influence into gates and the reservoir is also valid. Their diagonal and comb interaction weights are at most \(1/W\), and their remaining interaction weights are smaller. Therefore unsaturated types, whose infected masses remain their initial seeds, contribute at most \(K/W\) to any such target. This includes fractional seeds placed directly in gates or in the reservoir.
Padding a cover to exactly \(k\) vertices is permitted because \(k<n\). The proposed seeds use exactly \(n+k=K\) auxiliary units, respect every capacity, and activate the selected \(C_i,D_i\) types in the first update through their diagonal weight \(1\).
The level-\(j\) baseline influence calculation is correct. It counts:
The resulting influence is \(1-c_{ij}D+(3D/4)\mathbf1_{\{i\in S\}}\).
All subsequent activation margins are positive. A covered endpoint activates first; the other endpoint gains \(D\); selected nonendpoints need one endpoint activation; unselected nonendpoints need both.
This argument respects synchronous updates. Each newly activated gate supplies influence in a later update, and irreversibility preserves every previously saturated source. It does not require same-update propagation.
Once all gates saturate, the reservoir calculation gives influence at least \(1\). The YES-instance lower bound \(\mathrm{OPT}\ge M/T\) therefore follows.
The first-gate argument is valid. Before reservoir activation, if the first gate in an arm were to activate while its \(C_i\) remained unsaturated, there would be no saturated source inside that comb. Saturated sources elsewhere contribute at most \(dAW\), and unsaturated sources contribute at most \(K/W\). Their sum is below \(1\).
This also excludes simultaneous first activation of that gate and \(C_i\), because both thresholds use the preceding state.
When \(C_i\) first activates, its gates are still unsaturated. Its diagonal contribution is \(y_{C_i}\), and the remaining contributions satisfy the stated upper bound. Thus \(y_{C_i}\ge1-\eta\).
For \(D_i\), every off-diagonal weight is at most \(d\), so its first activation implies \(y_{D_i}\ge1-dB\ge1-\eta\).
Accordingly, \(K+1\) saturated types among the \(C_i,D_i\) would require more than \(K\) seed units. The claimed bound of at most \(K\) saturated clique types before reservoir activation follows for arbitrary real seed vectors.
The proof correctly examines the state immediately preceding the hypothetical first reservoir activation.
If \(C_1\) is unsaturated, its gates are unsaturated as well, and the reservoir influence is below \(1\).
If \(h\) other \(C_i\) types are unsaturated, there are \(n-h\) saturated \(C_i\) types. The preceding clique bound therefore permits at most \(k+h\) saturated \(D_i\) types. The reservoir upper bound simplifies correctly to \(1-hpD+3D/4+K/W\).
For \(h\ge1\), using \(p\ge1\) and \(K/W\le D/16\), this is strictly below \(1\). Thus every \(C_i\) must already be saturated.
Once every \(C_i\) is saturated, at most \(k\) types \(D_i\) are saturated. A missing gate outside arm \(1\) removes \(D\) from the all-saturated upper bound; a missing gate inside arm \(1\) removes \(bW>D\). The separate \(K/W\) allowance covers the remaining seed mass in the missing gate and all other unsaturated types.
Both cases leave influence strictly below \(1\). Hence reservoir activation requires every gate to have saturated beforehand.
Defining \(S\) from the hypothetical preactivation state is legitimate. Irreversibility ensures that every \(D_i\) saturated earlier also belongs to this fixed \(S\), and \(|S|\le k\).
For an uncovered edge \(e_j\), the induction correctly blocks every gate at levels \(j,\ldots,p\):
The induction applies to synchronous updates and includes all fractional seeds. It contradicts the necessary precondition that every gate saturate before the reservoir.
Thus the reservoir never activates in a NO instance. The resulting bound \(\mathrm{OPT}\le(AW+K)/T=B/T\) is justified.
The YES bound \(\mathrm{OPT}\ge3/4\) follows from \(T\ge4B\).
For fixed \(\varepsilon\), choosing a fixed integer \(r\ge1/\varepsilon\) gives \(T^\varepsilon\ge4B\). Therefore the stipulated approximation guarantee yields YES-instance spread at least \(3B/T\), whereas every feasible NO-instance spread is at most \(B/T\).
The strict separation is valid. The argument uses the requested factor \(Q^{1-\varepsilon}\), with \(Q=T\), rather than substituting support size or tree size for \(Q\).
The construction satisfies the input requirements:
The target \(\rho\) plays no role in the optimization objective and does not affect this approximation reduction.
The output-evaluation argument is valid under the ordinary binary encoding of rational seeds used in the write-up. Every changing update saturates at least one new type, so there are at most \(\tau\) changing updates. Each state coordinate is either an original seed or its capacity; exact rational threshold comparisons therefore have polynomial bit complexity.
The cited [finite-population paper](https://arxiv.org/pdf/1710.02827v2) is used as construction background, not as an asserted transfer theorem. The prover supplies the required separate argument for divisible seeds.
No additional clarification or repair is needed. The output resolves the assigned approximation question.
⟨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.