Answer: —
Theorem 1 — class: algorithmic
Given discrete update periods, a finite type set \(A\), rational type masses \(\mu_a^r\), finite-support contact laws, and a hyperparameter set \(\Theta\) with transmission function \(H\), each period generates a multitype configuration-model network. For a population-fraction budget \(\kappa\), compute feasible seed masses \(z_a^r\) with \(0\le z_a^r\le\mu_a^r\) and \(\sum_a z_a^r\le\kappa\) that maximize the worst-case limiting expected activated fraction \(\min_{\theta\in\Theta}\Phi_{\theta,r}(z^r)\); determine whether an additive-\(\varepsilon\) approximation can be maintained with useful amortized update time in the type and model parameters.
A society at period \(r\) is given by its support \(A^r\): the \(\tau_r\) types with positive binary-rational masses \(\mu_a^r\), normalized by \(\sum_a\mu_a^r=1\). Support size means the number of listed positive-mass types, not the number of possible types.
Each type has rational features \(x_a\in[-1,1]^{d/2}\), with even \(d\), and an explicitly listed rational probability law on nonnegative integer vectors \((i_b,o_b)_{b\in A^r}\) of incoming and outgoing contacts by neighbor type. Require \(\mu_a^r\mathbb E_a[o_b]=\mu_b^r\mathbb E_b[i_a]\) for every pair \(a,b\).
For each compatible population size \(N\), realize these type and contact frequencies exactly and match outgoing \(a\)-to-\(b\) stubs uniformly to incoming stubs from \(a\) at type \(b\); loops and parallel edges are allowed. Networks are sampled independently at each period.
Let \(\Theta=[-B,B]^d\), where \(B>0\) is rational, and \(H(\theta,x)=h(\theta^{\mathsf T}x)\), where the input link \(h:[-Bd,Bd]\to[0,1]\) is continuous, nondecreasing, \(1\)-Lipschitz, and piecewise linear with rational breakpoints and coefficients. An edge from type \(a\) to type \(b\) has IC transmission probability \(H(\theta,(x_a,x_b))\).
A seed vector \(z\) selects \(\lfloor Nz_a\rfloor\) vertices uniformly within each type, independently of contacts and the sampled network. Define \(\Phi_{\theta,r}(z)\) as the limit, along compatible \(N\), of the expected final activated fraction, including seeds; inputs are promised to have these limits for all \(\theta,z\).
For rational \(0<\kappa\le1\), put \(F_r(z)=\inf_{\theta\in\Theta}\Phi_{\theta,r}(z)\) and \(\mathrm{OPT}_r=\sup\{F_r(z):0\le z_a\le\mu_a^r,\ \sum_a z_a\le\kappa\}\). An \((\alpha,\beta,\varepsilon)\) approximation is a rational vector satisfying \(0\le z_a\le\mu_a^r\), \(\sum_a z_a\le\min\{1,\kappa/\beta\}\), and \(F_r(z)\ge\alpha\mathrm{OPT}_r-\varepsilon\), for \(0<\alpha,\beta\le1\) and \(0<\varepsilon<1\).
An update supplies a finite batch of type, mass, feature, or contact-law insertions, deletions, or replacements preserving these conditions; diffusion finishes before the next update. Let \(\tau\) be the maximum support size, \(m\) the maximum total number of listed contact-law outcomes, \(D\) the maximum total degree, \(L\) the maximum encoded snapshot bit length, and \(s\) the maximum update bit length.
Target. Which \((\alpha,\beta,\varepsilon)\) guarantees admit polynomial-time algorithms, and which are NP-hard, including the strict-budget additive case \((\alpha,\beta)=(1,1)\)?
For achievable guarantees, what preprocessing and amortized update bounds are possible in \(m,\tau,D,d,L,s,\kappa,\alpha,\beta,\varepsilon\), and \(\log(U/\delta)\), with simultaneous success probability at least \(1-\delta\) over an oblivious sequence of \(U\) updates?
Nearest known results. Finite-graph robust dynamic IC admits a randomized bicriteria guarantee: the union of \(T\) budget-\(k\) seed sets obtains a \(1-1/e\) factor reduced by history-dependent losses and accuracy terms, plus additive error, with an amortized update bound; its parameter sampling bound is exponential in \(d\). [Source](https://arxiv.org/html/2412.11827v1).
Static finite-graph hyperparametric robust IM has NP-hardness for proper robust solutions and algorithms allowing improper solutions. [Source](https://proceedings.mlr.press/v97/kalimeris19a.html). No result settling the precise mass-and-configuration-model approximation problem above was identified in the sources checked.
The full classification remains open. The following results substantially narrow it.
Write
$$
\rho=1-\frac1e,
\qquad
\gamma_\beta=1-e^{-1/\beta}.
$$
Proved results.
$$
F_r(z)\ge\gamma_\beta\mathrm{OPT}_r-\varepsilon
$$
within the expanded budget. Its running time is polynomial in the listed input parameters, $1/\kappa$, and $1/\varepsilon$ for every fixed $d$, and exponential in $d$. Explicit rebuilding bounds appear below.
$$
\beta(\alpha-\varepsilon)>\rho,
$$
finding an $(\alpha,\beta,\varepsilon)$ approximation is NP-hard. This holds already for $d=2$, deterministic contact laws, and constant transmission probability one.
$$
0<\varepsilon<\frac1e.
$$
The inverse-polynomial additive hardness from the notes also holds, with a complete reduction given below.
$$
\alpha-\varepsilon<\rho,
$$
and NP-hard whenever
$$
\alpha-\varepsilon>\rho.
$$
This does not settle the boundary, unrestricted dimension, or exponentially small binary-encoded budgets.
All algorithmic parameters supplied as input are assumed to have finite binary rational encodings. Let $b$ be their total encoding length.
Suppress the period index. Since seeds are activated and influence is at most one, the finite-population bounds and promised limits give
$$
\sum_a z_a\le F(z)\le1.
$$
Put
$$
c=\min\{1,\kappa/\beta\}.
$$
The rational vector $z_a=c\mu_a$ is feasible for the expanded budget and satisfies $F(z)\ge c$. Therefore it provides the requested guarantee whenever
$$
c\ge\alpha-\varepsilon.
$$
If $\kappa\ge\beta$, seeding the entire population solves every requested approximation guarantee.
Two further exact cases hold.
$$
F(z)=\sum_a z_a,\qquad \mathrm{OPT}=\kappa.
$$
Proportional seeding $z_a=\kappa\mu_a$ is optimal.
Conservative bit-operation bounds for these elementary algorithms are
$$
O((L+b+\tau)^3)
$$
for preprocessing and
$$
O((L+s+b+\tau)^3)
$$
per update. They are deterministic.
For a seed vector $z$, define the within-type fractions
$$
q_a=\frac{z_a}{\mu_a}.
$$
Preassign independent live-edge indicators with the IC transmission probabilities. A vertex activates exactly when its reverse reachable set contains a seed: a live path from a seed produces activation, and every nonseed activation has such a path.
Let a reverse reachable set contain $c_a$ vertices of type $a$. Write
$$
n_a=N\mu_a,\qquad s_a=\lfloor n_aq_a\rfloor.
$$
Under uniform fixed-count seeding, the probability that these vertices avoid seeds is
$$
A_{n_a}(c_a)=
\frac{\binom{n_a-c_a}{s_a}}{\binom{n_a}{s_a}},
$$
with value zero if the numerator is impossible. Under independent Bernoulli seeding, it is $(1-q_a)^{c_a}$.
For fixed $q_a$, these quantities become uniformly close over all $c_a$.
At $q_a=0$ or $q_a=1$, they agree exactly. For $0<q_a<1$, convergence holds uniformly for bounded $c_a$, by the finite product formula for the hypergeometric probability. Moreover,
$$
A_{n_a}(c_a)
\le(1-s_a/n_a)^{c_a}.
$$
For sufficiently large $N$, $s_a/n_a\ge q_a/2$. Thus, for $c_a>K$, both avoidance probabilities are bounded respectively by
$$
(1-q_a/2)^K
\quad\text{and}\quad
(1-q_a)^K.
$$
First take $N$ large for bounded counts, then take $K$ large.
For numbers in $[0,1]$, the difference between two products is bounded by the sum of the differences between corresponding factors. Since the support is finite, the total avoidance probabilities also become uniformly close. Averaging over networks, live edges, and target vertices proves equality of the limiting influence under the two seeding mechanisms.
This comparison is for each fixed seed vector; it asserts no uniform convergence as the seed vector varies.
For finite $y_a\ge0$, put
$$
z_a(y)=\mu_a(1-e^{-y_a}),
\qquad
G_\theta(y)=\Phi_\theta(z(y)),
\qquad
G(y)=\inf_{\theta\in\Theta}G_\theta(y).
$$
A reverse reachable set with count vector $c$ has Bernoulli activation probability
$$
1-e^{-c^{\mathsf T}y}.
$$
Its Hessian is
$$
-e^{-c^{\mathsf T}y}cc^{\mathsf T},
$$
which is negative semidefinite. Expectations and pointwise limits preserve concavity, so $G_\theta$ is concave. Furthermore,
$$
\begin{aligned}
G(\lambda y+(1-\lambda)w)
&\ge
\inf_\theta\bigl[\lambda G_\theta(y)+(1-\lambda)G_\theta(w)\bigr]\\
&\ge\lambda G(y)+(1-\lambda)G(w)
\end{aligned}
$$
for $0\le\lambda\le1$. Thus $G$ is concave.
Let $C=1/\beta$. Given any strict-budget seed vector, choose $y=Cq$. Then
$$
\sum_a\mu_ay_a=C\sum_a z_a\le C\kappa.
$$
For reverse reachable counts $c$, set $t=\sum_a c_aq_a$. The union bound gives
$$
1-\prod_a(1-q_a)^{c_a}\le\min\{1,t\}.
$$
Also,
$$
1-e^{-Ct}\ge(1-e^{-C})\min\{1,t\}.
$$
For $0\le t\le1$, this follows from concavity and the endpoint values; for $t\ge1$, it follows from monotonicity.
Taking expectations, limits, and parameter infima yields
$$
G(Cq)\ge\gamma_\beta F(z).
$$
Consequently,
$$
\sup_{\substack{y\ge0\\ \sum_a\mu_ay_a\le C\kappa}}G(y)
\ge\gamma_\beta\mathrm{OPT}.
$$
The remaining sections turn this structural comparison into an effective algorithm.
Suppose every type has Bernoulli seed probability at least $q_{\min}>0$. Consider two transmission matrices $p,p'$ satisfying
$$
\max_{a,b}|p_{ab}-p'_{ab}|\le\zeta.
$$
Couple the network, seeds, and edge uniforms. Explore reverse reachability from a target vertex, stopping immediately upon finding a seed. Skip previously visited vertices.
Conditionally on the exploration history, each newly inspected vertex is seeded with probability at least $q_{\min}$. Hence the expected number of inspected vertices is at most $1/q_{\min}$. Each inspected vertex requires testing at most $D$ incoming edges.
Before the first disagreement, the two coupled explorations coincide. At each tested edge, the conditional probability of a disagreement is at most $\zeta$. Summing these probabilities gives
$$
\left|
\mathbb E[\text{activated fraction under }p]
-
\mathbb E[\text{activated fraction under }p']
\right|
\le\frac{D\zeta}{q_{\min}}.
$$
The same argument applies to depth-truncated exploration. Passing to the population limits proves the corresponding bound for limiting influence.
In particular, on $y_a\ge a$ with $0<a\le1$,
$$
q_{\min}=1-e^{-a}\ge a/2,
$$
so the sensitivity bound is $2D\zeta/a$.
Let activation be counted only when a seed reaches the target by a live path of length at most $T$.
If full activation occurs but truncated activation does not, reverse exploration has reached depth $T+1$ without encountering a seed. Its depth-$T$ portion therefore contains at least $T+1$ distinct vertices. Under $y_a\ge a$, the probability that all these vertices avoid seeds is at most $e^{-a(T+1)}$.
Thus, at every finite population size under Bernoulli seeding,
$$
0\le
\text{full expected influence}
-
\text{depth-}T\text{ expected influence}
\le e^{-a(T+1)}.
$$
Let $\pi_a(\omega)$ be the probability of contact outcome $\omega$, and let
$$
e_{ab}=\mathbb E_a[o_b].
$$
When $e_{ab}>0$, a predecessor of type $a$ reached through an outgoing stub to type $b$ has contact law
$$
\pi_{a\mid b}(\omega)
=
\frac{\pi_a(\omega)o_b(\omega)}{e_{ab}}.
$$
This is a probability law because its numerator sums to $e_{ab}$.
Define messages
$$
u_{a\mid b}^{(0)}=e^{-y_a}
$$
and recursively
$$
u_{a\mid b}^{(t+1)}
=
e^{-y_a}
\sum_\omega\pi_{a\mid b}(\omega)
\prod_c
\left(1-p_{ca}+p_{ca}u_{c\mid a}^{(t)}\right)^{i_c(\omega)}.
$$
The depth-$T$ influence is, for $T\ge1$,
$$
f_{\theta,T}(y)
=
1-\sum_a\mu_ae^{-y_a}
\sum_\omega\pi_a(\omega)
\prod_c
\left(1-p_{ca}+p_{ca}u_{c\mid a}^{(T-1)}\right)^{i_c(\omega)}.
$$
For $T=0$, it is $\sum_a\mu_a(1-e^{-y_a})$.
Pairs with $e_{ca}=0$ never occur as incoming contacts with positive probability: this follows from balance and positive masses. Their messages need not be computed.
To justify the recursion, fix $T$. The reverse neighborhood contains at most
$$
1+D+\cdots+D^T
$$
vertices. Every nonempty stub pool has size proportional to $N$. With bounded degrees, the probability of a repeated vertex or previously exposed stub in this fixed exploration tends to zero. Sampling an outgoing stub gives exactly the displayed size-biased law. Sampling finitely many distinct stubs without replacement converges to independent sampling from these laws.
Thus the finite reverse neighborhood converges to the branching exploration described by the recursion. No incoming count is subtracted when a predecessor is reached: the selected stub is outgoing from that predecessor.
Together with Sections 2.1 and 3.2, this proves
$$
0\le G_\theta(y)-f_{\theta,T}(y)\le e^{-a(T+1)}
\qquad(y_a\ge a).
$$
The recursion represents an expectation of $1-e^{-c^{\mathsf T}y}$ over a finite-depth tree. Therefore $f_{\theta,T}$ is smooth and concave in $y$.
Writing $S=\sum_a c_a$, on $y_a\ge a$ its gradient satisfies
$$
\|\nabla f_{\theta,T}(y)\|_1
=
\mathbb E\!\left[S e^{-c^{\mathsf T}y}\right]
\le
\sup_{S\ge0}S e^{-aS}
=
\frac1{ea}.
$$
The same expectation argument gives, for full limiting influence,
$$
|G_\theta(y)-G_\theta(w)|
\le\frac{\|y-w\|_\infty}{ea}
$$
whenever both vectors have coordinates at least $a$. Taking infima preserves this bound.
The algorithm below achieves
$$
F(z)\ge\gamma_\beta\mathrm{OPT}-\varepsilon.
$$
If $\kappa/\beta\ge1$, seed the whole population. Otherwise set
$$
C=1/\beta,\qquad c=C\kappa<1,
$$
and choose
$$
a=\frac{\varepsilon c}{8},
\qquad
M=\left\lceil\log_2(16/\varepsilon)\right\rceil,
\qquad
T=\left\lceil M/a\right\rceil.
$$
Optimize on the rational polytope
$$
Y=
\left\{
y:\ a\le y_a\le M,\quad
\sum_a\mu_ay_a\le c
\right\}.
$$
It is nonempty because the constant vector $a$ belongs to it.
Take any original feasible $z$, with fractions $q$. The vector $Cq$ has linear cost at most $c$ and value at least $\gamma_\beta F(z)$.
Mix it with the constant vector $c$:
$$
\bar y=(1-\varepsilon/8)Cq+(\varepsilon/8)c\mathbf1.
$$
It remains feasible for the linear budget and has every coordinate at least $a$. Concavity and nonnegativity give
$$
G(\bar y)\ge(1-\varepsilon/8)G(Cq).
$$
Now replace each coordinate exceeding $M$ by $M$. For any reverse reachable set, if a changed coordinate occurs, its new no-seed probability is at most $e^{-M}$; otherwise nothing changes. Thus clipping loses at most $e^{-M}\le\varepsilon/16$, uniformly over parameters.
Taking the supremum over original feasible vectors proves
$$
\sup_{y\in Y}G(y)
\ge
\gamma_\beta\mathrm{OPT}-\frac{3\varepsilon}{16}.
$$
Set
$$
J=\max\left\{1,\left\lceil\frac{32D}{a\varepsilon}\right\rceil\right\}.
$$
For the univariate link, list its breakpoints and one rational preimage of every level $j/J$ lying in its range. These points partition its domain into intervals on which its value varies by at most $1/J$.
For every type pair, insert the corresponding hyperplanes
$$
\theta^{\mathsf T}(x_a,x_b)=t,
$$
and include the box facets $\theta_i=\pm B$. Their number is at most
$$
P=2d+\tau^2(L+J+2).
$$
Enumerate all intersections of $d$ linearly independent listed hyperplanes and retain those inside $\Theta$. Let $V$ be the resulting rational set; then
$$
|V|\le P^d.
$$
For any $\theta$, take the closure of an arrangement cell containing it. This is a nonempty bounded polytope, hence has a vertex. Every such vertex is an intersection of $d$ independent listed hyperplanes. At that vertex $v$, each transmission probability differs from its value at $\theta$ by at most $1/J$.
Section 3.1 consequently gives
$$
|G_\theta(y)-G_v(y)|
\le\frac{2D}{aJ}
\le\frac{\varepsilon}{16}
\qquad(y\in Y).
$$
This construction avoids a grid with size proportional to the numerical magnitude of $B$. Its vertices have bit lengths polynomial in $d$, $L$, and $\log J$, by rational Gaussian elimination.
Define
$$
\widehat G(y)=\min_{v\in V}f_{v,T}(y).
$$
It is concave, and the net and truncation bounds imply
$$
|\widehat G(y)-G(y)|\le\varepsilon/16
\qquad(y\in Y).
$$
Here is an explicit optimization argument.
Let
$$
R=\tau M,\qquad Q=2/a.
$$
The Euclidean diameter of $Y$ is at most $R$. Each oracle gradient has Euclidean norm at most $1/a$.
At a rational point $y$, evaluate every $f_{v,T}(y)$ to absolute error at most
$$
\nu=\varepsilon/128.
$$
Choose an index with minimum evaluated value, and approximate its gradient in Euclidean norm to error at most
$$
\xi=\frac{\varepsilon}{128\max\{R,1\}}.
$$
The resulting rational vector $g$ has norm at most $Q$ and satisfies
$$
\widehat G(w)
\le
\widehat G(y)+g^{\mathsf T}(w-y)+E
\qquad(w\in Y),
$$
where
$$
E=2\nu+R\xi\le3\varepsilon/128.
$$
Indeed, the selected function has true value within $2\nu$ of the minimum; its concavity supplies the tangent inequality, and the gradient error contributes at most $R\xi$.
Choose
$$
n=\left\lceil16RQ/\varepsilon\right\rceil,
\qquad
H=n^2,
\qquad
\lambda=\frac{R}{Qn}.
$$
Starting at any rational point in $Y$, iterate
$$
y_{t+1}=\operatorname{Proj}_Y(y_t+\lambda g_t).
$$
Projection is exactly computable using rational arithmetic. First clamp to the coordinate interval. If the weighted budget is violated, the projection has coordinates
$$
\min\{M,\max\{a,w_a-\ell\mu_a\}\},
$$
where $\ell\ge0$ is determined by the weighted-budget equality. The left side is piecewise linear in $\ell$ with rational breakpoints, so sorting these breakpoints finds the rational solution.
For a maximizer $y^\star$ of the continuous function $\widehat G$ on compact $Y$, projection and the approximate tangent inequality give
$$
\widehat G(y^\star)-\widehat G(y_t)
\le
\frac{\|y_t-y^\star\|_2^2-\|y_{t+1}-y^\star\|_2^2}{2\lambda}
+\frac{\lambda Q^2}{2}+E.
$$
Summing, dividing by $H$, and using concavity at the average $\bar y$ proves
$$
\max_Y\widehat G-\widehat G(\bar y)
\le\frac{RQ}{n}+E
<\varepsilon/8.
$$
The oracle values and gradients have polynomial bit complexity. In fact, the recursion and differentiation use
$$
O\!\left(Tm\tau^2(D+1)\right)
$$
scalar arithmetic operations per parameter point. A depth-$T$ tree has at most $(D+1)^{T+1}$ vertices, so intermediate derivative magnitudes have logarithms polynomial in $T\log(D+1)$. Induction through the product recursions shows that sufficient working precision is polynomial in
$$
T,\ L,\ d,\ \log(m+\tau+D+1),\ \log(1/\nu),\ \log(1/\xi).
$$
Products have factors in $[0,1]$, and the size-biased coefficients form probability laws; accumulated rounding errors are bounded by an exponential in $T$ with polynomially bounded logarithm.
Finally, $e^{-y_a}$ can be approximated with certified rational bounds in polynomial time: the Taylor series for $e^{y_a}$ has remainder at most
$$
e^M\frac{M^{r+1}}{(r+1)!},
$$
and $r=O(M+p)$ suffices for $p$ bits of accuracy, after which reciprocation gives $e^{-y_a}$. Thus this oracle does not assume exact real arithmetic.
Approximate $1-e^{-\bar y_a}$ from below by a dyadic rational $\tilde q_a$ so accurately that
$$
0\le
\bar y_a+\log(1-\tilde q_a)
\le a\varepsilon/32.
$$
This requires only polynomial precision because $\bar y_a\le M$.
Output
$$
z_a=\mu_a\tilde q_a.
$$
It is rational and obeys
$$
\sum_a z_a
\le
\sum_a\mu_a(1-e^{-\bar y_a})
\le
\sum_a\mu_a\bar y_a
\le c.
$$
Its logarithmic coordinates remain at least $a/2$. Section 3.4 bounds the influence loss from rounding by $\varepsilon/16$.
Combining the restriction loss, the two oracle comparisons, optimization error, and output rounding gives
$$
F(z)\ge\gamma_\beta\mathrm{OPT}-\varepsilon.
$$
The sum of the displayed losses is at most $\varepsilon/2$, leaving room within the stated error.
The construction uses at most $P^d$ parameter points and
$$
H=
O\!\left(\frac{\tau^2M^2}{a^2\varepsilon^2}\right)
$$
optimization iterations. Its main scalar-arithmetic count is bounded by
$$
O\!\left(
P^d H
\left[Tm\tau^2(D+1)+\tau\log(\tau+1)\right]
\right),
$$
plus parameter-net construction and input processing. The preceding precision argument converts this into a bit-operation bound polynomial in the same quantities and encoded input lengths.
A simpler conservative summary is obtained by defining
$$
W=
L+b+m+\tau+D+d+
\kappa^{-1}+\beta^{-1}+\varepsilon^{-1}+2.
$$
Preprocessing takes
$$
W^{O(d+1)}
$$
bit operations, with an absolute implicit constant.
After each update, reconstruct the snapshot and rerun the algorithm. Replacing $L+b$ by $L+s+b$ in $W$ gives the same sufficient bound per update and hence amortized per update.
These algorithms are deterministic. Their guarantees hold simultaneously over every valid sequence of updates, with probability one. Therefore no dependence on $\log(U/\delta)$ is needed.
Scope of polynomiality. This is polynomial time for fixed $d$ in the numerical reciprocals $1/\kappa$ and $1/\varepsilon$, and in $D$. It is not a polynomial bound in the encoded input length when these numerical quantities are exponentially large.
More generally, if
$$
\alpha-\varepsilon<\gamma_\beta,
$$
run the algorithm with a positive internal accuracy smaller than
$$
\gamma_\beta-(\alpha-\varepsilon).
$$
Since $\mathrm{OPT}\le1$, this supplies the requested $(\alpha,\beta,\varepsilon)$ guarantee. The runtime then depends on the reciprocal of that internal accuracy.
This construction proves fixed-additive-error hardness and handles fractional seeding explicitly.
Let $S_1,\ldots,S_t$ be sets on a nonempty universe of size $u$, and let $1\le k\le t$. Choose a power of two $n\ge t+u$, and put
$$
v=\left\lfloor\frac{n-t}{u}\right\rfloor,
\qquad
w=\frac vn,
\qquad
\kappa=\frac kn.
$$
Create:
All listed masses are positive dyadic rationals and sum to one.
For each incidence $e\in S_j$, every root vertex has $v$ outgoing stubs to $b_e$, and every terminal vertex has one incoming stub from $a_j$. The balance equation is
$$
\frac1n\,v=w\cdot1.
$$
All contact laws are deterministic. Roots have no incoming contacts, and terminals have no outgoing contacts.
Take $d=2$, $B=1$, zero features, and $h\equiv1$.
For compatible $N$, a terminal vertex’s predecessor from root type $a_j$ is uniform in that root type. Matchings for distinct pairs are independent. Hence, writing $q_a=z_a/\mu_a$, limiting influence is
$$
F(z)=
\frac1n\sum_jq_{a_j}
+
w\sum_e
\left[
1-(1-q_{b_e})\prod_{j:e\in S_j}(1-q_{a_j})
\right]
+
\mu_{\mathrm{iso}}q_{\mathrm{iso}},
$$
with the last term omitted when there is no isolated type. Floors converge to these fractions, so every required limit exists.
Define root-only fractional coverage
$$
C(q)=
\sum_e\left[1-\prod_{j:e\in S_j}(1-q_j)\right],
$$
and let $C_k^\star$ be maximum integral coverage by $k$ sets. The influence formula implies
$$
F(z)\le\sum_a z_a+wC(q_{\mathrm{roots}}).
$$
The function $C$ is coordinatewise nondecreasing and multilinear. For distinct $i,j$,
$$
\frac{\partial^2 C}{\partial q_i\partial q_j}
=
-\sum_{e:i,j\in\{j:e\in S_j\}}
\prod_{\ell:e\in S_\ell,\ \ell\ne i,j}(1-q_\ell)
\le0.
$$
Along $q+\lambda e_i-\lambda e_j$, the second derivative is therefore nonnegative. One endpoint of the feasible exchange interval has value at least the current value and makes at least one coordinate integral.
Fill the root-coordinate sum to $k$, then repeat these exchanges. At most one fractional coordinate remains; the integer coordinate sum excludes that possibility. Consequently,
$$
\sum_jq_j\le k
\quad\Longrightarrow\quad
C(q)\le C_k^\star.
$$
Under strict budget, $\sum_jq_{a_j}\le k$. Thus
$$
F(z)\le\kappa+wC_k^\star.
$$
Seeding $k$ optimal roots completely attains this bound. Therefore
$$
\mathrm{OPT}=\kappa+wC_k^\star.
$$
For every $K\ge k$,
$$
\sum_jq_j\le K
\quad\Longrightarrow\quad
C(q)\le\frac Kk C_k^\star.
$$
To prove this, first consider an integral collection of $\ell\ge k$ sets. A uniformly random $k$-subset covers each element covered by the collection with probability at least $k/\ell$: fix one set covering that element and use its inclusion probability. Thus
$$
C(\text{collection})\le\frac{\ell}{k}C_k^\star.
$$
If $K\le t$, fill the fractional sum to $K$ and perform the preceding exchanges. At most one coordinate remains fractional. By multilinearity, its value is a convex combination of integral solutions of sizes $\lfloor K\rfloor$ and $\lceil K\rceil$. Both sizes are at least $k$, and their weighted average is $K$, proving the bound.
If $K\ge t$, monotonicity and the integral bound for all $t$ sets prove it directly.
An expanded-budget output consequently satisfies
$$
F(z)\le\frac{\kappa}{\beta}
+\frac{w}{\beta}C_k^\star.
$$
The external theorem used is the perfect-completeness maximum-coverage gap: for every fixed $\eta>0$, it is NP-hard to distinguish instances in which $k$ sets cover the whole universe from instances in which every $k$ sets cover at most a $\rho+\eta$ fraction. This is Feige’s maximum-coverage theorem; its precise gap formulation is also stated in Section 4.5 of [Feige and Vondrák](https://theoryofcomputing.org/articles/v006a011/v006a011.pdf).
Fix rational $\alpha,\beta,\varepsilon$ satisfying
$$
\beta(\alpha-\varepsilon)>\rho.
$$
Choose a fixed rational $\rho'$ with
$$
\rho<\rho'<\beta(\alpha-\varepsilon),
$$
and use the gap theorem with soundness at most $\rho'$. Set
$$
g=\alpha-\varepsilon-\rho'/\beta>0.
$$
In the weighted construction, choose $n$ as the smallest power of two satisfying
$$
n\ge
\max\left\{
t+u,\,
\frac{4(t+u+k/\beta)}g
\right\}.
$$
This is polynomially bounded because the approximation parameters and $g$ are fixed constants. The construction has at most $t+u+1$ types and $D\le\max\{n,t\}$.
Also,
$$
wu
=
\frac{u\lfloor(n-t)/u\rfloor}{n}
\ge1-\frac{t+u}{n}.
$$
In a yes instance,
$$
\mathrm{OPT}=\kappa+wu,
$$
so a successful approximation must have value at least
$$
A=\alpha(\kappa+wu)-\varepsilon.
$$
In a no instance, every expanded-budget output has value at most
$$
B=\frac{\kappa}{\beta}+\frac{\rho'}{\beta}wu.
$$
Their separation is
$$
\begin{aligned}
A-B
&=(\alpha-\rho'/\beta)wu-\varepsilon
-(1/\beta-\alpha)\kappa\\
&\ge g-\frac{t+u+k/\beta}{n}\\
&\ge3g/4>0.
\end{aligned}
$$
All thresholds are rational. Output feasibility and its influence can be checked exactly from the displayed polynomial. Comparing with $(A+B)/2$ decides the NP-hard gap problem.
Thus the requested approximation is NP-hard under the stated condition. Fractional root seeding, direct terminal seeding, random matching, and normalized masses are all accounted for.
For randomized algorithms with success probability at least $2/3$, the same check has one-sided error: no feasible output on a no instance crosses the threshold. Such an algorithm would imply $\mathrm{NP}=\mathrm{RP}$.
Taking $\beta=\alpha=1$ proves fixed additive hardness for every rational $\varepsilon<1/e$.
For completeness, the finer additive hardness requires no coverage gap theorem.
Use Vertex Cover, which is NP-complete by [Karp’s completeness theorem](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9). Restrict to nontrivial instances with at least one edge and $1\le k\le|V|$.
Create one root type per vertex and one terminal type per edge. Give all types mass $1/n$, where $n$ is the smallest power of two at least $|V|+|E|$, adding isolated types to reach $n$ types. Every incidence has one outgoing root stub and one incoming terminal stub. Again take $h\equiv1$ and zero features.
The proof of Section 6 gives
$$
\mathrm{OPT}=\frac{k+C_k^\star}{n}.
$$
Put
$$
T_0=\frac{k+|E|}{n}.
$$
A yes instance has optimum $T_0$; a no instance has optimum at most $T_0-1/n$.
With
$$
\varepsilon=\frac1{4n}=\frac1{4\tau},
$$
a strict-budget additive approximation has value greater than $T_0-1/(2n)$ on yes instances, whereas every feasible vector has smaller value on no instances. Exact evaluation decides Vertex Cover.
Here $m=\tau$, $d=2$, and all construction sizes are polynomial.
The following distinctions remain essential.
$$ 1-e^{-1/\beta} \quad\text{and}\quad \frac{1-1/e}{\beta}. $$
Static hardness applies to dynamic algorithms with polynomial preprocessing and polynomial update time: the hard snapshot may be supplied initially, or introduced through a polynomial-size replacement batch.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial partial results. Its structural algorithmic argument and coverage reductions are sound in substance. I found no false central step. However, it does not resolve the full classification requested in USER_TASK, and several implementation and accuracy statements need minor clarification.
The appropriate overall status is partial. This agrees with the prover’s explicit statement that the full classification remains open.
The limiting bounds
$$
\sum_a z_a\le F(z)\le 1
$$
are correct. At finite population size, the seed contribution is $\sum_a\lfloor Nz_a\rfloor/N$, which converges to $\sum_a z_a$. Taking the parameter infimum preserves these bounds.
Proportional seeding with $z_a=c\mu_a$ is feasible and provides value at least $c$. Consequently, the stated sufficient condition $c\ge\alpha-\varepsilon$ is valid because $\mathrm{OPT}\le1$.
Both exact special cases are correct:
The conservative elementary running-time bounds are consistent with rational arithmetic and the output size.
The hypergeometric avoidance formula is correct, including its zero convention. The endpoint cases $q_a=0$ and $q_a=1$ agree exactly.
For an interior fixed fraction, the displayed exponential tail bound and convergence for bounded counts establish uniform convergence over all reverse-reachable counts. The product comparison then establishes equality of limiting influence for each fixed seed vector.
The qualification that this is not uniform convergence over varying seed vectors is appropriate. Subsequent uses do not require such stronger convergence.
For a fixed reverse-reachable count vector, the activation probability and Hessian are correctly computed:
$$
1-e^{-c^{\mathsf T}y},
\qquad
-e^{-c^{\mathsf T}y}cc^{\mathsf T}.
$$
Expectations and pointwise limits preserve the concavity inequality. The displayed argument for taking the parameter infimum is also correct. Thus both $G_\theta$ and $G$ are concave.
The union bound and the inequality
$$
1-e^{-Ct}\ge(1-e^{-C})\min\{1,t\}
$$
hold throughout the stated range. The linear budget calculation is correct.
Consequently, the structural comparison
$$
\sup_{\substack{y\ge0\\\sum_a\mu_ay_a\le C\kappa}}G(y)
\ge\gamma_\beta\mathrm{OPT}
$$
is established. No attainment assumption for the original supremum is needed.
The exploration argument is valid under Bernoulli seeding. Previously uninspected seed indicators remain independent of the exploration history. Before the first edge disagreement, both explorations coincide, and each newly tested edge has disagreement probability at most $\zeta$.
The expected inspection bound therefore gives the stated sensitivity estimate. Loops and parallel edges do not invalidate it: previously visited vertices can be skipped, while the incoming-edge count remains bounded by $D$.
If a target activates only through paths longer than $T$, a shortest successful path contains at least $T+1$ distinct vertices in its depth-$T$ portion. Failure of truncated activation requires all those vertices to be unseeded.
Since the live neighborhood is independent of Bernoulli seeds, the bound
$$
e^{-a(T+1)}
$$
is valid, uniformly over finite population sizes.
The size-biased law is correctly normalized. Balance and positive masses justify omitting pairs with zero outgoing expectation.
The message recursion uses the correct contact counts. In particular, the selected predecessor stub is outgoing, so subtracting an incoming stub would be erroneous; the prover correctly does not subtract one.
For each fixed depth, the explored neighborhood has bounded size, and each relevant stub pool grows linearly with population size. This justifies the vanishing collision probability and asymptotic independence needed for the branching recursion.
The truncation estimate then correctly connects the recursion to the promised full influence limits.
The finite-depth expectation representation establishes smoothness and concavity. The gradient estimate
$$
\|\nabla f_{\theta,T}(y)\|_1\le\frac1{ea}
$$
is correct. The corresponding Lipschitz estimate for full limiting influence follows by passing the uniform finite-population inequality to the limit.
The polytope is nonempty, and mixing preserves its linear budget while imposing the required lower coordinate bound.
The clipping argument is correct: whenever a clipped coordinate occurs in a reverse-reachable set, the clipped avoidance probability is at most $e^{-M}$. Hence clipping loses at most that amount.
Because
$$
M\ge\log_2(16/\varepsilon),
$$
the bound $e^{-M}\le\varepsilon/16$ holds. The total restriction loss of $3\varepsilon/16$ is valid.
The arrangement argument is sound once degenerate equations are handled as noted below. A bounded arrangement-cell closure has a vertex, and the link values differ by at most $1/J$ within its closure.
The sensitivity estimate then gives the claimed parameter error. The construction depends on the encoded size of $B$, rather than its numerical magnitude.
Minor issue — degenerate equations. Features may be zero, so some listed equations have zero normal vector. Such equations can describe the whole space or the empty set, rather than a hyperplane. The write-up needs to state how these equations are handled before referring to their arrangement. This is a routine construction detail; box facets still provide vertices.
The stated uniform comparison between $\widehat G$ and $G$ is correct: parameter discretization controls the upper error, and truncation controls the lower error.
The approximate tangent inequality correctly accounts for selecting an approximately minimizing parameter and approximating its gradient.
The projection formula is correct. The weighted-budget equation is piecewise linear with rational breakpoints, so exact rational projection is possible.
The projected ascent inequality, telescoping sum, and concavity at the averaged iterate give the claimed optimization error. The choices of $n$, $H$, and $\lambda$ have consistent constants.
The recurrence and its differentiated form have the stated polynomial scalar-operation count. The bound on finite-depth tree size supports polynomial working precision. The exponential approximation argument is also correct in substance.
Minor issue — bit-complexity justification is compressed. The write-up asserts, rather than displays, the rounding-error induction and does not explicitly bound the growth of exact rational iterate denominators through repeated projections and averaging.
The minimum clarification needed is an explicit error-propagation bound for values and gradients, together with a bound on the bit lengths of projected iterates. These are routine implementation estimates; the omission does not undermine the structural algorithm.
Approximating seed probabilities from below preserves feasibility. The logarithmic-coordinate error bound keeps the rounded coordinates above $a/2$, permitting the stated Lipschitz estimate.
The final loss accounting is correct:
$$
\frac{3\varepsilon}{16}
+\frac{2\varepsilon}{16}
+\frac{\varepsilon}{8}
+\frac{\varepsilon}{16}
=\frac{\varepsilon}{2}.
$$
Thus the displayed argument supports the claimed $\gamma_\beta$ guarantee with additive error $\varepsilon$, subject to the routine numerical clarification above.
Rebuilding after every update supplies a valid preprocessing and amortized update bound. Determinism supplies simultaneous success with probability one, so omitting dependence on $\log(U/\delta)$ is justified.
The output correctly distinguishes polynomial dependence on numerical parameters from polynomial dependence on their binary encoding lengths.
Minor issue — internal accuracy condition. Section 5 states that choosing internal accuracy smaller than
$$
\gamma_\beta-(\alpha-\varepsilon)
$$
supplies the requested guarantee.
As stated, that condition alone is insufficient when $\alpha<\gamma_\beta$. The comparison requiring justification is
$$
(\gamma_\beta-\alpha)\mathrm{OPT}+\varepsilon-\eta\ge0,
$$
where $\eta$ is the internal error. Using only $\mathrm{OPT}\le1$ does not establish this for every internal accuracy allowed by the stated rule.
The claimed existence of a suitable internal accuracy remains valid. The prover must state an accuracy choice sufficient throughout the full allowed range of $\mathrm{OPT}$.
The statement about achievable strict-budget guarantees should also specify whether the approximation triple is fixed. For varying encoded triples, the later dependence on the reciprocal of the threshold margin remains part of the running time.
The construction meets the input conditions:
The displayed influence formula is correct. Matchings for distinct ordered type pairs are independent, and each relevant predecessor has the appropriate root seed probability.
The bound separating seed mass and root coverage correctly accounts for direct terminal seeding.
The mixed partial derivative has the correct sign. Along a budget-preserving exchange, the coverage function is convex, so an endpoint can be chosen without decreasing coverage.
For integer budget $k$, repeated exchanges eliminate all fractional coordinates. This establishes
$$
C(q)\le C_k^\star.
$$
The resulting exact optimum
$$
\mathrm{OPT}=\kappa+wC_k^\star
$$
is valid.
For augmented budgets, the random-subset bound and the final fractional-coordinate interpolation correctly prove
$$
C(q)\le\frac KkC_k^\star.
$$
The cases $K\le t$ and $K\ge t$ are both covered.
The cited perfect-completeness maximum-coverage gap is stated with the needed hypotheses. Section 4.5 of the cited paper explicitly confirms that distinguishing full coverage by $k$ sets from coverage at most $1-1/e+\eta$ is NP-hard. [Feige and Vondrák, Section 4.5](https://theoryofcomputing.org/articles/v006a011/v006a011.pdf).
Choosing $\rho'$ strictly between the two thresholds is legitimate. With fixed approximation parameters, $g$ is a positive constant, so the constructed $n$ is polynomially bounded.
The mass estimate, yes-instance lower threshold, no-instance upper threshold, and separation calculation are all correct. The degree bound also holds: root degree is at most $uv\le n-t$, and terminal degree is at most $t$.
Exact rational evaluation of the output influence is polynomial in the encoded output and instance sizes. Therefore the reduction establishes the stated hardness condition.
The randomized conclusion is justified by feasibility checking and the fact that no feasible no-instance output crosses the threshold.
Taking $\alpha=\beta=1$ correctly yields fixed additive hardness for every permitted rational $\varepsilon<1/e$.
The Vertex Cover reduction correctly specializes coverage to incident-edge coverage.
Adding isolated types gives $\tau=n$, and all masses equal $1/n$. The exact optimum formula supplies the claimed gap of $1/n$.
The selected error
$$
\varepsilon=\frac1{4n}
$$
leaves a strict separation around the stated decision threshold. The reduction therefore establishes inverse-polynomial additive hardness with polynomial construction size.
The output does not provide the complete classification requested by USER_TASK. It explicitly leaves unresolved:
These are substantive scope limitations, rather than errors in the proved reductions. Rebuilding nevertheless answers the request for possible update bounds within the algorithm’s stated regime; proving improved maintenance bounds is not necessary to validate that result.
Another round is warranted. The established results are substantial, and the identified proof-writing issues require clarification rather than a replacement argument.
⟨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.