Answer: \(\mathrm{NP}\)-hard, already for \(d=1\), with dyadic rational inputs and an inverse-polynomial threshold gap.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe time-critical influence maximization problem is NP-hard for the IC-M model.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), rational meeting probabilities \(m_{st}\), transmission intensities \(P_{st}\), a deadline \(d\), seed-mass budget \(\kappa\), and threshold \(\rho\), does there exist \(x_t\in[0,\mu_t]\) with \(\sum_t x_t\le\kappa\) whose limiting expected active fraction by step \(d\) is at least \(\rho\)? For the IC-M version, set \(z_t=x_t/\mu_t\), \(q_t(0)=z_t\), \(q_t(-1)=0\), and \(\Delta q_t(a)=q_t(a)-q_t(a-1)\); for \(r=1,\ldots,d\), require \(q_t(r)=z_t+(1-z_t)\left[1-\exp\left(-\sum_{s\in T}\mu_sP_{st}\sum_{a=0}^{r-1}\Delta q_s(a)(1-(1-m_{st})^{r-a})\right)\right]\), and test whether \(\sum_t\mu_tq_t(d)\ge\rho\).
A society is given by its support: a nonempty list \(T\) 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.
For ordered type pairs, including equal types, input binary rational meeting probabilities \(m_{st}\in[0,1]\) and transmission intensities \(P_{st}\ge0\); omitted pairs have zero intensity. Let \(m\) count the explicitly supplied pairs and \(L\) be the total input bit length. Input also a positive integer deadline \(d\), encoded in binary, and binary rationals \(0<\kappa\le1\) and \(\rho\in[0,1]\).
A seed allocation consists of real masses \(x_t\in[0,\mu_t]\) satisfying \(\sum_t x_t\le\kappa\). Set \(z_t=x_t/\mu_t\), \(q_t(-1)=0\), \(q_t(0)=z_t\), and \(\Delta q_t(a)=q_t(a)-q_t(a-1)\).
Define the active fractions recursively, for \(1\le r\le d\), by
\(q_t(r)=z_t+(1-z_t)\left[1-\exp\left(-\sum_{s\in T}\mu_sP_{st}\sum_{a=0}^{r-1}\Delta q_s(a)\bigl(1-(1-m_{st})^{r-a}\bigr)\right)\right].\)
An allocation qualifies exactly when \(\sum_t\mu_tq_t(d)\ge\rho\), including equality.
Is deciding whether a qualifying allocation exists in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? Measure running times in \(m,\tau,L\), and \(\log(d+1)\).
Discrete time-critical IC-M influence maximization is NP-hard: seeds activate initially, and each active agent independently meets each inactive neighbor at every subsequent step, with one independent transmission attempt at their first meeting. [Source](https://arxiv.org/abs/1204.3074).
Continuous marketing strategies on finite agent networks have approximation guarantees under different diffusion definitions. [Source](https://ojs.aaai.org/index.php/AAAI/article/view/5332). No result settling the exact distributional recurrence above was located.
The decision problem is \(\mathrm{NP}\)-hard, already for \(d=1\) and with every explicitly supplied meeting probability equal to \(1\).
The reduction below allows arbitrary real seed allocations and uses only dyadic rational input parameters. It separates yes and no instances by an inverse-polynomial gap, so exact equality at the threshold causes no difficulty.
Let \(G\) be a nonempty simple undirected graph on \(n\) vertices, with adjacency matrix \(A\), and let \(B=I+A\). Write \(\alpha(G)\) for its maximum independent-set size.
Lemma. For every nonnegative vector \(y\) with \(\sum_i y_i=u\),
\(y^{\mathsf T}By\ge u^2/\alpha(G)\).
Equality is attained by assigning \(u/\alpha(G)\) to each vertex of a maximum independent set and zero elsewhere.
Proof. The case \(u=0\) is immediate. Suppose two adjacent vertices \(i,j\) both have positive coordinates. Hold all other coordinates fixed and redistribute their total \(y_i+y_j\) between them.
Because \(B_{ii}=B_{jj}=B_{ij}=B_{ji}=1\), their internal contribution is
\(y_i^2+y_j^2+2y_iy_j=(y_i+y_j)^2\),
which stays constant. Their interactions with the remaining coordinates are affine in \(y_i\), with \(y_j=y_i+y_j-y_i\). An affine function on this redistribution interval has a minimum at an endpoint. Consequently, one can set one of these two coordinates to zero without increasing the quadratic form.
Repeating this operation eventually produces a vector \(y'\) whose positive support is an independent set, while preserving its total mass and satisfying \(y'^{\mathsf T}By'\le y^{\mathsf T}By\). If that support has size \(r\), then \(r\le\alpha(G)\), and Cauchy–Schwarz gives
\(y^{\mathsf T}By\ge y'^{\mathsf T}By'=\sum_i(y'_i)^2\ge u^2/r\ge u^2/\alpha(G)\).
The stated equality construction follows directly. \(\square\)
Reduce from Independent Set: given \(G\) and an integer \(k\), decide whether \(\alpha(G)\ge k\). We restrict to \(n\ge2\) and \(2\le k\le n\); the excluded cases are decidable immediately, so this restriction preserves \(\mathrm{NP}\)-hardness.
First pad the graph until its vertex count \(n\) is a power of two. Each added vertex is adjacent to every other vertex, including every other added vertex. An independent set containing an added vertex has size one, so padding preserves \(\alpha(G)\). It increases the vertex count by less than a factor of two.
Create one type for each graph vertex and one additional type \(\star\). Set
\(\mu_i=h=1/(2n)\), \(\mu_\star=1/2\), \(\kappa=h\), and \(d=1\).
These positive masses sum to one.
For each vertex \(i\), define
\(r_i=\sum_j B_{ij}=1+\deg_G(i)\), and \(b_i=(n-r_i)/n\).
Thus \(0\le b_i\le1\). Choose
\(\varepsilon=2^{-a}\),
where \(a\) is the smallest integer such that \(2^a\ge2k(k-1)\). Consequently,
\(1/[4k(k-1)]\le\varepsilon\le1/[2k(k-1)]\).
Supply the following intensities, always with meeting probability \(1\):
All other intensities are zero. In particular, \(\star\) has no outgoing transmission. The diagonal entries of \(B\) use the equal-type pairs permitted by the task.
The balancing identity is
\(\sum_t\mu_tP_{it}=\varepsilon\bigl(hr_i+\tfrac12b_i\bigr)=\varepsilon/2\).
Every graph type therefore has the same mass-weighted outgoing intensity.
Consider any feasible allocation. Write \(x=(x_1,\ldots,x_n)\) for its graph-type coordinates and define
\(v=x_\star\), \(u=\sum_i x_i\), and \(w=u+v\le\kappa\).
At deadline \(1\), the recurrence simplifies exactly to
\(q_t(1)=1-(1-x_t/\mu_t)e^{-a_t}\),
where
\(a_t=\sum_s x_sP_{st}\).
Hence the total active mass is
\(F(x,v)=\sum_t\mu_tq_t(1)=w+\sum_t(\mu_t-x_t)(1-e^{-a_t})\).
The construction gives
\(a_j=\varepsilon\sum_iB_{ij}x_i\), and \(a_\star=\varepsilon\sum_i b_ix_i\).
It also gives the identities
\(\sum_t\mu_ta_t=\varepsilon u/2\),
\(\sum_t x_ta_t=\varepsilon x^{\mathsf T}Bx+\varepsilon v\sum_i b_ix_i\).
Every intensity is at most \(\varepsilon\), so \(0\le a_t\le\varepsilon u\le\varepsilon\kappa\).
For every \(a\ge0\),
\(a-a^2/2\le1-e^{-a}\le a\).
Indeed, integrate \(1-s\le e^{-s}\le1\) over \(0\le s\le a\). Since all \(\mu_t-x_t\) are nonnegative, these inequalities imply
\(F(x,v)\le w+\varepsilon u/2-\varepsilon x^{\mathsf T}Bx-\varepsilon v\sum_i b_ix_i\),
and
\(F(x,v)\ge w+\varepsilon u/2-\varepsilon x^{\mathsf T}Bx-\varepsilon v\sum_i b_ix_i-\varepsilon^2\kappa^2/2\).
For the lower bound, the total error is at most
\(\tfrac12\sum_t(\mu_t-x_t)a_t^2\le\tfrac12\sum_t\mu_ta_t^2\le\varepsilon^2\kappa^2/2\),
using \(\sum_t\mu_t=1\).
These bounds include allocations that seed the balancing type.
For each positive integer \(j\), define
\(H_j=\kappa+\varepsilon\kappa/2-\varepsilon\kappa^2/j\),
and let
\(\delta=H_k-H_{k-1}=\varepsilon\kappa^2/[k(k-1)]>0\).
Suppose \(\alpha(G)\ge k\). Choose an independent set of size \(k\), seed each of its types with mass \(\kappa/k\), and seed every other type with zero.
This allocation is feasible because \(\kappa/k\le\mu_i=\kappa\). It has \(u=w=\kappa\), \(v=0\), and
\(x^{\mathsf T}Bx=\kappa^2/k\).
The lower bound therefore gives
\(F(x,0)\ge H_k-\varepsilon^2\kappa^2/2\ge H_k-\delta/4\).
The last inequality follows from \(\varepsilon\le1/[2k(k-1)]\).
Suppose \(\alpha(G)\le k-1\). The quadratic lemma gives, for every feasible allocation,
\(x^{\mathsf T}Bx\ge u^2/(k-1)\).
Dropping the nonpositive balancing term from the upper bound yields
\(F(x,v)\le\kappa+\varepsilon\bigl(u/2-u^2/(k-1)\bigr)\).
The function \(g(u)=u/2-u^2/(k-1)\) is nondecreasing on \(0\le u\le\kappa\): throughout this interval,
\(g'(u)=1/2-2u/(k-1)\ge1/2-1/[n(k-1)]\ge0\).
Consequently, every feasible allocation satisfies
\(F(x,v)\le H_{k-1}=H_k-\delta\).
We now choose the actual input threshold without evaluating any exponential.
The bounds on \(\varepsilon\), together with \(k\le n\), imply
\(\delta\ge1/[16n^2k^2(k-1)^2]\ge1/(16n^6)\).
Set \(R=128n^6\), which is a power of two because \(n\) is a power of two. Define
\(\rho=\lceil R(H_k-\delta/2)\rceil/R\).
Then \(\rho\) is dyadic rational and
\(H_k-\delta/2\le\rho\le H_k-\delta/2+1/R\le H_k-3\delta/8\).
Thus:
The threshold is valid. Indeed, \(\kappa\le1/4\) implies \(H_{k-1}\ge\kappa>0\), so \(\rho>0\). Also,
\(\rho<H_k\le\kappa(1+\varepsilon/2)\le9/32<1\).
We have proved the exact equivalence
\(\alpha(G)\ge k\quad\Longleftrightarrow\quad\text{the constructed society has a qualifying allocation}\).
There are \(\tau=n+1\) types and at most \(m=n^2+n\) supplied pairs. Every output rational is dyadic and has \(O(\log n)\) bits. This includes \(\rho\): its denominator \(R=128n^6\) has \(O(\log n)\) bits, and its numerator is computed by exact rational arithmetic.
The construction has total encoding length \(L=O(n^2\log n)\) and is computable in polynomial time. The deadline is \(d=1\), so \(\log(d+1)\) is constant.
This is a polynomial-time many-one reduction proving \(\mathrm{NP}\)-hardness for the exact stated recurrence. A polynomial-time algorithm in \(m,\tau,L,\log(d+1)\) would therefore imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output proves the claimed \(\mathrm{NP}\)-hardness. The reduction applies to arbitrary real allocations, handles seeds assigned to the additional type, and separates yes and no instances strictly. I found no major or minor issues requiring repair.
For adjacent vertices \(i,j\), fixing their total coordinate mass makes their internal contribution constant because all four relevant entries of \(B\) equal \(1\). Interactions with other coordinates are affine in the redistributed coordinate, so an endpoint achieves a value no larger than the starting value.
Each operation removes at least one positive coordinate and introduces none. Thus the procedure terminates with independent positive support. For \(u>0\), its size \(r\) satisfies \(1\le r\le\alpha(G)\), and Cauchy–Schwarz gives the stated lower bound. The case \(u=0\) is handled explicitly. The equality construction also checks out.
The excluded Independent Set cases are immediately decidable. Restricting to \(n\ge2\) and \(2\le k\le n\) therefore preserves hardness.
Every added vertex is universal, so any independent set containing one has size \(1\). Since the original graph is nonempty, its independence number is at least \(1\); consequently padding preserves \(\alpha(G)\). Padding to the next power of two increases the vertex count by less than a factor of two. The subsequent use of \(n\) as the padded vertex count is consistent.
There are \(n\) graph types of mass \(1/(2n)\) and one additional type of mass \(1/2\). Their masses are positive and sum to \(1\). The budget \(\kappa=1/(2n)\) and deadline \(d=1\) are valid.
Since \(1\le r_i\le n\), the quantities \(b_i=(n-r_i)/n\) are nonnegative and at most \(1\). All supplied intensities are nonnegative and at most \(\varepsilon\), and every supplied meeting probability equals \(1\). Equal-type pairs are expressly allowed by the task.
Minimality of \(a\) gives the stated bounds on \(\varepsilon\). The balancing identity is exact:
\(\varepsilon(hr_i+b_i/2)=\varepsilon/2\).
At \(d=1\), the only increment is \(\Delta q_s(0)=z_s\), and the meeting factor for every supplied pair is \(1\). Thus the exponent is exactly \(a_t=\sum_s x_sP_{st}\).
Substitution into the recurrence gives the stated expression for \(F(x,v)\). The formulas for \(a_j\), \(a_\star\), \(\sum_t\mu_ta_t\), and \(\sum_t x_ta_t\) follow directly from the supplied intensities and balancing identity.
The bound \(a_t\le\varepsilon u\le\varepsilon\kappa\) is valid because the additional type has no outgoing intensity. In particular, these computations cover allocations with \(v>0\).
Integrating \(1-s\le e^{-s}\le1\) on the indicated interval proves
\(a-a^2/2\le1-e^{-a}\le a\) for every \(a\ge0\).
Feasibility ensures \(\mu_t-x_t\ge0\), so multiplying by these coefficients preserves the inequality directions. The total lower-bound error is at most \(\varepsilon^2\kappa^2/2\), using \(a_t\le\varepsilon\kappa\) and total mass \(1\). No assumption about rational seed coordinates is used.
Seeding an independent set of size \(k\) equally is feasible, uses the entire budget, and gives \(x^{\mathsf T}Bx=\kappa^2/k\).
The claimed error comparison follows from
\((\varepsilon^2\kappa^2/2)/\delta=\varepsilon k(k-1)/2\le1/4\).
Hence the displayed lower bound \(F(x,0)\ge H_k-\delta/4\) is justified.
When \(\alpha(G)\le k-1\), the lemma implies
\(x^{\mathsf T}Bx\ge u^2/(k-1)\). The balancing term is nonpositive in the upper bound because \(v,b_i,x_i\ge0\), so dropping it is legitimate. Replacing \(w\) by \(\kappa\) also preserves the upper bound.
On \(0\le u\le\kappa\), the derivative satisfies
\(g'(u)\ge1/2-1/[n(k-1)]\ge0\).
This includes the boundary case \(n=k=2\), where the lower bound is zero. Therefore the maximum of this upper bound occurs at \(u=\kappa\), yielding \(F(x,v)\le H_{k-1}\).
The gap satisfies
\(\delta\ge1/[16n^2k^2(k-1)^2]\ge1/(16n^6)\).
Consequently \(1/R\le\delta/8\). The ceiling definition therefore places \(\rho\) between \(H_k-\delta/2\) and \(H_k-3\delta/8\).
Combining these inequalities with the allocation bounds gives the claimed yes-instance margin \(\delta/8\) and no-instance margin \(\delta/2\). Thus inclusion of equality in the qualification condition does not affect the reduction.
Positivity follows from \(H_{k-1}\ge\kappa>0\). Also, \(\varepsilon\le1/4\) and \(\kappa\le1/4\) give \(\rho<H_k\le9/32<1\). The threshold is a valid input.
Power-of-two padding makes all supplied parameters dyadic. Although the intermediate expressions involving \(k\) need not be dyadic, exact rational arithmetic computes the ceiling defining \(\rho\); the resulting threshold has denominator \(R\) and numerator of \(O(\log n)\) bits.
There are at most \(n^2+n\) supplied pairs, each with \(O(\log n)\)-bit parameters. The total construction size and construction time are polynomial. Since \(d=1\), the deadline parameter contributes constant \(\log(d+1)\).
The established equivalence is therefore a polynomial-time many-one reduction to the exact decision problem. It proves \(\mathrm{NP}\)-hardness; membership in \(\mathrm{NP}\) is neither claimed nor needed.
No additional clarification or mathematical argument is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.