Answer: \(\mathrm{NP}\)-hard, even for \(H=1\) and \(K=d=2\)
Theorem 2 — class: hardness
The K-complex contagion influence maximiza- tion problem is NP-hard. The proof can be done by showing that a special instance of K-complex contagion is an arbitrary instance of the IC model. Consider a special instance of K-complex contagion when K = 1. In this instance, the cascade probability p(k) in Eq.(1) becomes a constant value that does not depend on k: p(k) = p0.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(R=\{1,\ldots,\tau\}\), rational masses \(\mu_i\), a rational contact kernel \(P\), degree \(d\), complex-contagion parameters \(K,p_0,p_1\), seed-mass budget \(\beta\), horizon \(H\), and target \(Q\), choose rational seed masses \(x_i\) with \(0\le x_i\le\mu_i\) and \(\sum_i x_i\le\beta\). Starting from \(y_i^{(0)}=x_i\), let \(q_i(y)=\sum_jP_{ij}y_j/\mu_j\), \(\rho(q)=p_1+(p_0-p_1)\sum_{\ell=K}^{d}\binom{d}{\ell}q^\ell(1-q)^{d-\ell}\), and \(y_i^{(r+1)}=y_i^{(r)}+(\mu_i-y_i^{(r)})\rho(q_i(y^{(r)}))\). Decide whether \(\Phi_H(x)=\sum_i y_i^{(H)}\ge Q\), or optimize \(\Phi_H(x)\).
Definitions. Let \(R=\{1,\ldots, au\}\), with rational \(\mu_i>0\), a row-stochastic rational matrix \(P\), integers \(1\le K\le d\) and \(H\), and rationals \(0\le p_1\le p_0\le1\), \(eta,Q\ge0\). A feasible seed vector has rational \(0\le x_i\le\mu_i\) and \(\sum_i x_i\leeta\). Set \(y_i^{(0)}=x_i\), \(q_i(y)=\sum_jP_{ij}y_j/\mu_j\), \( ho(q)=p_1+(p_0-p_1)\sum_{\ell=K}^{d}inom{d}{\ell}q^\ell(1-q)^{d-\ell}\), and \(y_i^{(r+1)}=y_i^{(r)}+(\mu_i-y_i^{(r)}) ho(q_i(y^{(r)}))\). Define \(\Phi_H(x)=\sum_i y_i^{(H)}\). The decision problem asks whether some feasible \(x\) satisfies \(\Phi_H(x)\ge Q\).
Target. Is this mass-distribution complex-contagion influence-maximization problem NP-hard, or is it solvable in polynomial time?
Nearest known results. Discrete \(K\)-complex-contagion influence maximization with a cardinality seed budget is NP-hard. No result on the exact mass-distribution formulation above is supplied.
The mass-distribution complex-contagion influence-maximization problem is \(\mathrm{NP}\)-hard. Hardness already holds under the fixed parameters
\[ H=1,\qquad K=d=2,\qquad p_1=0,\qquad p_0=1. \]
Thus the hardness is not caused by a large horizon or by binary encoding of \(H\) or \(d\). Unless \(\mathrm P=\mathrm{NP}\), the problem is not polynomial-time solvable.
We reduce from Clique on regular graphs.
This problem is \(\mathrm{NP}\)-hard: Independent Set is \(\mathrm{NP}\)-complete on \(3\)-regular simple graphs. If \(G_0\) is \(3\)-regular on \(n\) vertices, then its complement \(G=\overline{G_0}\) is \((n-4)\)-regular, and a set is independent in \(G_0\) if and only if it is a clique in \(G\).
Let \(G=(V,E)\) be an \(r\)-regular graph, with \(n=|V|\), and let \(k\le n\) be the requested clique size.
Set
\[ M=4(n+k+1)^2. \]
Create one population type for every vertex, one for every edge, and one additional sink type \(s\):
\[ R=V\mathbin{\dot\cup}E\mathbin{\dot\cup}\{s\}. \]
The masses are
\[ \mu_u=1\quad(u\in V),\qquad \mu_e=M\quad(e\in E),\qquad \mu_s=M. \]
Define the row-stochastic matrix \(P\) as follows.
For every edge type \(e=\{u,v\}\),
\[ P_{e,u}=P_{e,v}=\frac12. \]
For every \(i\in V\cup\{s\}\), set
\[ P_{i,s}=1. \]
All unspecified entries are zero. Every row therefore sums to one.
Finally, set
\[ \beta=k,\qquad H=1,\qquad K=d=2,\qquad p_1=0,\qquad p_0=1, \]
and set the target to
\[ Q=k+\frac M4\bigl(rk+k(k-1)\bigr). \]
For these fixed contagion parameters,
\[ \rho(q)=\binom22q^2=q^2. \]
Write
\[ z_u=x_u\quad(u\in V),\qquad a_e=x_e\quad(e\in E),\qquad b=x_s,\qquad t=\frac bM. \]
Because vertex masses are one, \(0\le z_u\le1\). The budget constraint is
\[ \sum_{u\in V}z_u+\sum_{e\in E}a_e+b\le k. \]
For an edge type \(e=\{u,v\}\),
\[ q_e(x)=\frac{z_u+z_v}{2}. \]
For every vertex type and for the sink,
\[ q_i(x)=t. \]
Consequently,
\[ \Phi_1(x) = \sum_{i\in R}x_i + \frac14\sum_{\{u,v\}\in E}(M-a_{\{u,v\}})(z_u+z_v)^2 + t^2\left(\sum_{u\in V}(1-z_u)+(M-b)\right). \]
Define
\[ F(z)=\sum_{\{u,v\}\in E}(z_u+z_v)^2 \]
on the polytope
\[ C_k=\left\{z\in[0,1]^V:\sum_{u\in V}z_u\le k\right\}. \]
If \(G\) has no clique of size \(k\), then every \(z\in C_k\) satisfies
\[ F(z)\le rk+k(k-1)-2. \]
The function \(F\) is convex because it is a sum of squares of linear functions.
Every extreme point of \(C_k\) is a \(0\)-\(1\) vector. Indeed, if an extreme point had two fractional coordinates, they could be perturbed in opposite directions. If it had exactly one fractional coordinate and the budget inequality were not tight, that coordinate could be perturbed alone. If the budget inequality were tight, the fractional coordinate would equal the integer \(k\) minus a sum of \(0\)-\(1\) coordinates, which is impossible.
A convex function on a polytope is bounded above by its largest value at an extreme point. It therefore suffices to consider \(z=\mathbf1_S\), where \(S\subseteq V\) and \(|S|\le k\).
Let \(e(S)\) be the number of edges with both endpoints in \(S\), and let \(\delta(S)\) be the edge boundary of \(S\). Then
\[ F(\mathbf1_S)=4e(S)+|\delta(S)|. \]
Since \(G\) is \(r\)-regular,
\[ r|S|=2e(S)+|\delta(S)|, \]
and hence
\[ F(\mathbf1_S)=r|S|+2e(S). \]
If \(|S|=k\), absence of a \(k\)-clique gives
\[ e(S)\le\binom{k}{2}-1. \]
Therefore
\[ F(\mathbf1_S) \le rk+2\left(\binom{k}{2}-1\right) =rk+k(k-1)-2. \]
If \(|S|<k\), extend \(S\) to a \(k\)-element set \(T\). The function \(F\) is coordinatewise nondecreasing on \([0,1]^V\), so
\[ F(\mathbf1_S)\le F(\mathbf1_T)\le rk+k(k-1)-2. \]
Convexity now gives the asserted bound for every \(z\in C_k\). \(\square\)
Let \(S\) be such a clique. Seed every vertex type in \(S\) to its full mass:
\[ z_u= \begin{cases} 1,&u\in S,\\ 0,&u\notin S, \end{cases} \qquad a_e=0,\qquad b=0. \]
This is a rational feasible vector of total seed mass \(k\).
Because \(S\) is a clique,
\[ e(S)=\binom{k}{2}, \]
so regularity gives
\[ F(\mathbf1_S)=rk+2\binom{k}{2}=rk+k(k-1). \]
The sink contribution is zero. Therefore
\[ \Phi_1(x) = k+\frac M4\bigl(rk+k(k-1)\bigr) =Q. \]
Thus the constructed instance is a yes-instance.
Consider any feasible seed vector, even allowing real rather than merely rational coordinates. Since \(M-a_e\le M\), the edge-type contribution is at most
\[ \frac M4F(z) \le \frac M4\bigl(rk+k(k-1)-2\bigr). \]
The direct seed contribution is at most \(k\).
The remaining sink-dependent contribution \(D\) satisfies
\[ D \le \left(\frac{k}{M}\right)^2(n+M) = \frac{k^2n}{M^2}+\frac{k^2}{M}. \]
Writing \(N=n+k+1\), so that \(M=4N^2\), and using \(n,k<N\), gives
\[ D < \frac{1}{16N}+\frac14 <1. \]
On the other hand,
\[ \frac M2=2N^2>1, \]
and hence \(D<M/2\). Therefore
\[ \begin{aligned} \Phi_1(x) &\le k+\frac M4\bigl(rk+k(k-1)-2\bigr)+D\\ &< k+\frac M4\bigl(rk+k(k-1)-2\bigr)+\frac M2\\ &= k+\frac M4\bigl(rk+k(k-1)\bigr)\\ &=Q. \end{aligned} \]
Thus no feasible seed vector reaches \(Q\).
The construction has \(n+|E|+1\) types. Its only nonintegral matrix entries are \(1/2\), and \(M\) and \(Q\) have polynomial binary encoding length. It is therefore computable in polynomial time.
The reduction has a strict gap in the no-case and supplies a rational \(0\)-\(1\) seed vector in the yes-case. Thus the restriction to rational seed vectors causes no difficulty.
The exact mass-distribution formulation is \(\mathrm{NP}\)-hard, even for a single diffusion round and the fixed genuinely complex threshold \(K=d=2\). The discrete hardness result is not being transferred by analogy; the proof above is a direct reduction for the continuous mass-distribution model.
The proof establishes hardness but does not establish membership in \(\mathrm{NP}\) for the unrestricted formulation, where rational witnesses are not given an explicit encoding-length bound.
⟨structured verdict parsed — rendered above⟩
The prover gives a valid polynomial-time many-one reduction establishing \(\mathrm{NP}\)-hardness, even with \(H=1\), \(K=d=2\), \(p_1=0\), and \(p_0=1\). The construction correctly handles continuous rational seed allocations rather than merely importing discrete influence-maximization hardness.
No substantive mathematical gaps or incorrect steps were found.
The reduction from Clique on regular graphs is justified by complementing a \(3\)-regular Independent Set instance. If \(G_0\) has \(n\) vertices and degree \(3\), then every vertex has degree \(n-4\) in \(\overline{G_0}\), and independent sets in \(G_0\) are exactly cliques in its complement. Thus the stated regular-graph Clique source problem is \(\mathrm{NP}\)-hard.
The type set, masses, transition matrix, budget, horizon, contagion parameters, and target are all valid inputs.
Every row of \(P\) sums to one:
With \(K=d=2\), \(p_1=0\), and \(p_0=1\), the response function correctly reduces to
\[ \rho(q)=q^2. \]
For an edge \(e=\{u,v\}\),
\[ q_e(x)=\frac{z_u+z_v}{2}, \]
because the endpoint masses equal \(1\).
For every vertex type and the sink,
\[ q_i(x)=\frac{b}{M}=t. \]
Substituting these quantities into the one-round update gives exactly the displayed formula for \(\Phi_1(x)\). The edge increment, vertex increments, sink increment, and direct seed mass are all accounted for once.
The function
\[ F(z)=\sum_{\{u,v\}\in E}(z_u+z_v)^2 \]
is convex as a sum of squares of linear functions.
The characterization of the extreme points of
\[ C_k=\left\{z\in[0,1]^V:\sum_u z_u\le k\right\} \]
as \(0\)-\(1\) vectors is correct because \(k\) is integral. A point in a compact polytope is a convex combination of extreme points, so convexity implies that its value cannot exceed the largest value at an extreme point.
For \(z=\mathbf 1_S\), the calculation
\[ F(\mathbf 1_S)=4e(S)+|\delta(S)|=r|S|+2e(S) \]
is correct.
If \(|S|=k\) and there is no \(k\)-clique, then
\[ e(S)\le \binom{k}{2}-1, \]
which yields the claimed gap of \(2\). If \(|S|<k\), extending \(S\) to a \(k\)-element set is legitimate because \(k\le n\), and coordinatewise monotonicity of \(F\) supplies the same bound.
Thus the convexity lemma is established.
Seeding precisely the vertices of a \(k\)-clique is feasible and uses total mass \(k\). Regularity and the clique property give
\[ F(\mathbf 1_S)=rk+k(k-1). \]
The sink-dependent contribution vanishes, and the resulting objective equals \(Q\). Hence every yes-instance of the source problem maps to a yes-instance.
For every feasible seed vector, the vertex coordinates satisfy \(z\in C_k\). Since \(a_e\ge0\),
\[ M-a_e\le M, \]
so the entire edge increment is bounded by \(MF(z)/4\). The direct seed contribution is at most \(k\).
Because \(b\le k\), the remaining sink-dependent contribution satisfies
\[ D\le \left(\frac{k}{M}\right)^2(n+M). \]
With \(M=4(n+k+1)^2\), the prover correctly obtains \(D<1<M/2\). Combined with the gap of \(2\) in \(F\), this gives the strict inequality
\[ \Phi_1(x)<Q. \]
The argument applies even to real feasible vectors, so it certainly excludes all rational feasible vectors.
The construction uses polynomially many types and entries. The integers \(M\) and \(Q\) have polynomial binary encoding length. The reduction is therefore polynomial-time.
The proof establishes \(\mathrm{NP}\)-hardness without needing membership in \(\mathrm{NP}\). The prover correctly avoids claiming \(\mathrm{NP}\)-completeness.
⟨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.