Answer: \(\mathrm{NP}\)-hard for every fixed \(\alpha\in(0,1]\), already with \(m=2\) and \(s=1\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-hard to compute an α-approximation to the problem max|S|≤k POV(S) for any α > 0, even for two candidates and even when the instance is deterministic.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given two candidates \(c^\star,c_1\), a finite set \(T\) of complete voter-and-network-block types, a rational distribution \(\mu\in\mathbb{Q}_{\ge0}^{T}\) with \(\sum_t\mu_t=1\), a finite scenario distribution \(\rho\), typed kernels \(\lambda^\omega_{ut}\), and seed fraction \(\kappa\), choose \(x_t\in[0,\mu_t]\) with \(\sum_t x_t\le\kappa\) to maximize \(\Pr_{\omega\sim\rho}[2\sum_{t:\pi_t(2)=c^\star}r_t^\omega(x)>a_1-a_\star]\), where \(a_c=\sum_{t:\pi_t(1)=c}\mu_t\) and \(r^\omega(x)\) is the least fixed point of \(r_t=x_t+(\mu_t-x_t)(1-e^{-\sum_u\lambda^\omega_{ut}r_u})\); return an optimum or an \(\alpha\)-approximation.
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. There are \(m=2\) candidates, \(c^\star,c_1\). Each type specifies a strict ranking \(\pi_t\) and a network block; distinct blocks may have identical rankings.
The input explicitly lists \(s\ge1\) scenarios \(\Omega\), positive binary-rational probabilities \(\rho_\omega\) summing to \(1\), and finite nonnegative binary-rational influence intensities \(\lambda^\omega_{ut}\) from type \(u\) to type \(t\). The seed budget is a binary rational \(\kappa\in[0,1]\).
Choose seed masses \(x_t\in[0,\mu_t]\) with \(\sum_t x_t\le\kappa\), before the scenario is drawn. Every type may be seeded and transmit influence, including types already ranking \(c^\star\) first.
In scenario \(\omega\), the influenced masses \(r^\omega(x)\) are the coordinatewise least fixed point in \(\prod_t[0,\mu_t]\) of \(r_t=x_t+(\mu_t-x_t)(1-\exp(-\sum_u\lambda^\omega_{ut}r_u))\). Influenced voters promote \(c^\star\) one position; those already ranking it first retain their vote. Ties count as failure.
Define \(a_c=\sum_{t:\pi_t(1)=c}\mu_t\) and maximize \(F(x)=\sum_{\omega\in\Omega}\rho_\omega\mathbf{1}\{2\sum_{t:\pi_t(2)=c^\star}r_t^\omega(x)>a_{c_1}-a_{c^\star}\}\). Let \(\mathrm{OPT}\) be the supremum over feasible real seed vectors. Algorithms use the Turing bit model and output binary-rational feasible seed vectors; inequalities have their exact mathematical meaning, without a tolerance or margin promise. Let \(L\) be the total input bit length.
For each fixed \(\alpha\in(0,1]\), is obtaining a feasible \(x\) with \(F(x)\ge\alpha\mathrm{OPT}\) polynomial-time solvable in \(m,\tau,s,L\), or NP-hard?
For finite voters with independent-cascade diffusion, obtaining any positive multiplicative approximation to probability of victory is NP-hard, even with two candidates and deterministic propagation. [Wilder and Vorobeychik](https://www.cais.usc.edu/wp-content/uploads/2018/01/aamas_elections_final.pdf)
No result settling this explicitly represented scenario model with fractional seeds and the exponential least-fixed-point dynamics was identified in the literature search.
For every fixed \(\alpha\in(0,1]\), obtaining the requested approximation is \(\mathrm{NP}\)-hard, already with \(m=2\) and a single scenario \(s=1\).
The proof below handles arbitrary fractional seeds, permits seeding every type, and avoids evaluating transcendental expressions when decoding an algorithm’s output.
We reduce from Independent Set on simple cubic graphs. An instance consists of a simple undirected graph \(G=(V,E)\), with every vertex having degree three, and an integer \(k\). The question is whether \(G\) contains an independent set of size at least \(k\). This problem is \(\mathrm{NP}\)-hard; see Theorem 3.2 and the discussion extending the result to graphs of degree exactly three in [Alimonti and Kann, *Hardness of Approximating Problems on Cubic Graphs*](https://www.cs.yale.edu/homes/aspnes/pinewiki/attachments/MarkovChains/alimanti-mis-cubic.pdf).
Write \(n=|V|\). We restrict to \(1\le k\le n\), since instances outside this range are trivial.
For a positive rational \(h\), define
\( P_k=\{z\in[0,h]^V:\sum_{v\in V}z_v\le kh\} \)
and
\( Q(z)=3h\sum_{v\in V}z_v-2\sum_{\{u,v\}\in E}z_uz_v. \)
Rounding lemma. For every \(z\in P_k\), there is a subset \(A\subseteq V\), with \(|A|\le k\), such that
\( Q(z)\le Q(h\mathbf 1_A)=h^2(3|A|-2e(A)), \)
where \(e(A)\) denotes the number of edges with both endpoints in \(A\).
Proof. Suppose two coordinates \(z_i,z_j\) lie strictly between zero and \(h\). Replace them by \(z_i+t,z_j-t\), allowing \(t\) to range over the closed interval on which both coordinates remain in \([0,h]\). This preserves the total seed mass.
If \(\{i,j\}\notin E\), the resulting function of \(t\) is affine. If \(\{i,j\}\in E\), its quadratic term is \(2t^2\), because the contribution of that edge is
\( -2(z_i+t)(z_j-t). \)
All other contributions are affine in \(t\). Thus the function is convex, and at least one endpoint has value no smaller than its value at \(t=0\). At either endpoint, at least one of the two coordinates becomes zero or \(h\).
Repeating this operation leaves at most one coordinate strictly between zero and \(h\), without decreasing \(Q\).
If one such coordinate remains and there are \(j\) coordinates equal to \(h\), feasibility implies \(j\le k-1\). Consequently, the remaining coordinate can vary throughout \([0,h]\) while preserving feasibility. Since \(Q\) is affine in that coordinate, setting it to zero or \(h\) can again avoid decreasing \(Q\). The resulting vector is \(h\mathbf 1_A\), with \(|A|\le k\). Substitution gives the stated formula. \(\square\)
Two consequences will be used:
\( Q(z)\le(3k-2)h^2. \)
For the second consequence, apply the lemma. If \(|A|\le k-1\), then \(3|A|-2e(A)\le3k-3\). If \(|A|=k\), then \(e(A)\ge1\), giving the bound \(3k-2\).
Let \(N\) be the smallest power of two satisfying \(N\ge n\). Set
\( h=\frac1{8N},\qquad \ell=\frac1{128N},\qquad \kappa=kh, \)
and define the rational victory threshold
\( \theta=\kappa+\ell(3k-1)h^2. \)
Construct \(n+2\) types, each with its own network block:
\( \mu_b=\frac12+\theta-nh. \)
\( \mu_p=\frac12-\theta. \)
There is one scenario, of probability one. For each graph edge \(\{u,v\}\in E\), put intensity \(\ell\) in both directions between the corresponding vertex types. Every other intensity is zero.
All types remain seedable.
We verify that this is a valid input. First, \(nh\le1/8\), so \(\kappa\le1/8\). Also \(3\ell h<1\), and therefore
\( 0<\theta <\kappa(1+3\ell h) <2\kappa \le\frac14. \)
Hence both auxiliary masses are positive. The masses sum to one.
All numerical parameters are dyadic rationals with bit length \(O(\log n)\). The support size is \(\tau=n+2\); even explicitly listing the entire intensity matrix takes only polynomial space and time.
The initial mass supporting \(c_1\) is
\( B=nh+\mu_b=\frac12+\theta, \)
and the initial mass supporting \(c^\star\) is \(1-B\). Thus, writing
\( S(x)=\sum_{v\in V}r_v(x)+r_b(x), \)
the exact victory condition is
\( 2S(x)>B-(1-B)=2\theta, \)
or equivalently \(S(x)>\theta\).
Fix any feasible seed vector. Write \(z_v=x_v\) for its vertex coordinates.
Because the auxiliary types are isolated,
\( r_b=x_b,\qquad r_p=x_p. \)
On the vertex types, the fixed-point equations are
\( r_v=z_v+(h-z_v)\left(1-\exp\left(-\ell\sum_{u\in N_G(v)}r_u\right)\right). \)
These equations have a unique fixed point in \([0,h]^V\). Indeed, their right-hand side maps this box into itself. Since \(a\mapsto1-e^{-a}\) is Lipschitz with constant one on the nonnegative reals, the map has Lipschitz constant at most \(3\ell h<1\) in the maximum norm. The contraction mapping theorem therefore applies. In particular, this unique fixed point is the stipulated least fixed point.
We next prove the uniform estimate
\( \left|\sum_{v\in V}r_v-\sum_{v\in V}z_v-\ell Q(z)\right|\le\mathcal E, \qquad \mathcal E=\frac{27}{2}n\ell^2h^3. \)
Define
\( \delta_v=r_v-z_v,\qquad a_v=\ell\sum_{u\in N_G(v)}r_u. \)
Since \(0\le r_u\le h\) and each vertex has three neighbors,
\( 0\le a_v\le3\ell h. \)
Using \(0\le1-e^{-a}\le a\) for \(a\ge0\), we obtain
\( 0\le\delta_v=(h-z_v)(1-e^{-a_v})\le3\ell h^2. \)
Also, for every \(a\ge0\),
\( |1-e^{-a}-a|\le\frac{a^2}{2}. \)
For completeness, the difference satisfies
\(
a-(1-e^{-a})=\int_0^a(1-e^{-t})\,dt,
\)
which lies between zero and \(\int_0^a t\,dt=a^2/2\).
Consequently,
\( \delta_v-\ell(h-z_v)\sum_{u\in N_G(v)}z_u = (h-z_v)\left((1-e^{-a_v})-a_v+\ell\sum_{u\in N_G(v)}\delta_u\right). \)
Its absolute value is at most
\( h\left(\frac{(3\ell h)^2}{2}+\ell\cdot3\cdot3\ell h^2\right) = \frac{27}{2}\ell^2h^3. \)
Summing over vertices proves the estimate, because cubic regularity gives
\( \sum_v(h-z_v)\sum_{u\in N_G(v)}z_u = 3h\sum_vz_v-2\sum_{\{u,v\}\in E}z_uz_v = Q(z). \)
Finally, the error is smaller than the required gap:
\( \frac{\mathcal E}{\ell h^2} = \frac{27}{2}n\ell h \le\frac{27}{256} <\frac14, \)
where we used \(n\le N\), \(\ell=1/(128N)\), and \(h\le1\). Thus
\( \mathcal E<\frac14\ell h^2. \)
Suppose \(G\) contains an independent set \(A\) of size \(k\). Fully seed its vertex types:
\( z=h\mathbf1_A,\qquad x_b=x_p=0. \)
This is a feasible binary-rational vector, and \(Q(z)=3kh^2\). The uniform estimate yields
\( S(x)\ge\kappa+3k\ell h^2-\mathcal E = \theta+\ell h^2-\mathcal E >\theta. \)
Thus this seed vector wins, and \(\mathrm{OPT}=1\).
Suppose \(G\) has no independent set of size \(k\). Consider any feasible real seed vector.
Its vertex coordinates belong to \(P_k\). Moreover, the budget constraint gives
\( \sum_vz_v+x_b\le\kappa. \)
This remains true when some budget is spent on the initially preferred type \(p\).
Using the uniform estimate and the rounding lemma,
\( S(x) \le \sum_vz_v+x_b+\ell Q(z)+\mathcal E \le \kappa+\ell(3k-2)h^2+\mathcal E. \)
Therefore,
\( S(x)\le\theta-\ell h^2+\mathcal E<\theta. \)
No feasible real seed vector wins, and \(\mathrm{OPT}=0\).
This proves that deciding whether \(\mathrm{OPT}>0\) is \(\mathrm{NP}\)-hard in the constructed single-scenario family.
Fix any \(\alpha\in(0,1]\). Suppose a polynomial-time algorithm outputs a feasible binary-rational vector \(x\) satisfying
\( F(x)\ge\alpha\mathrm{OPT}. \)
Because there is one scenario, \(F(x)\in\{0,1\}\). On every yes-instance, \(\mathrm{OPT}=1\), so the algorithm must output a winning vector.
We must still explain how to distinguish the source instances in polynomial time from that vector. Directly testing the exponential victory inequality could raise exact-comparison difficulties. The reduction avoids this issue.
Compute the rational number \(Q(z)\) from the output’s vertex coordinates and accept precisely when
\( Q(z)>\left(3k-\frac32\right)h^2. \)
On a no-instance, the rounding lemma guarantees
\( Q(z)\le(3k-2)h^2 < \left(3k-\frac32\right)h^2, \)
so the test rejects.
On a yes-instance, the output must satisfy \(S(x)>\theta\). The uniform upper bound and budget constraint imply
\( \theta<S(x)\le\kappa+\ell Q(z)+\mathcal E. \)
Hence
\( Q(z)> \frac{\theta-\kappa-\mathcal E}{\ell} = (3k-1)h^2-\frac{\mathcal E}{\ell} > \left(3k-\frac54\right)h^2 > \left(3k-\frac32\right)h^2. \)
Thus the test accepts.
The output of a polynomial-time Turing algorithm has polynomial bit length. Evaluating \(Q(z)\) and comparing these rationals therefore takes polynomial time.
The hypothetical approximation algorithm would consequently decide Independent Set on cubic graphs in polynomial time. This establishes the claimed \(\mathrm{NP}\)-hardness for every fixed positive approximation factor. The proof does not require an exact transcendental comparison oracle or a margin promise on the general input.
⟨structured verdict parsed — rendered above⟩
The proof resolves the assigned question. The reduction handles arbitrary real fractional seeds, respects the least-fixed-point semantics, and gives a polynomial-time rational test for decoding the approximation algorithm’s output. I found no major or minor mathematical issues.
The required source problem is Independent Set on simple graphs in which every vertex has degree exactly three. The cited paper’s Theorem 3.2 establishes APX-completeness for maximum degree three, and its subsequent discussion explicitly extends the results to degree exactly three. Thus the citation supports the NP-hard source problem used here. [Alimonti and Kann, Theorem 3.2 and the discussion on page 5](https://www.cs.yale.edu/homes/aspnes/pinewiki/attachments/MarkovChains/alimanti-mis-cubic.pdf).
Restricting to integer thresholds \(1\le k\le n\) removes only trivial instances. Cubic regularity supplies both properties subsequently needed: exactly three neighbors per vertex and the identity involving \(Q\).
The pairwise rounding argument is valid.
For two fractional coordinates, the allowed interval of \(t\) is closed, contains zero, and preserves both coordinate bounds and total mass. For a nonedge, the objective is affine in \(t\). For an edge, the contribution
\(-2(z_i+t)(z_j-t)\) has quadratic coefficient \(2\), so the objective is convex. In either case, an endpoint has objective at least its value at zero.
Each operation reduces the number of fractional coordinates by at least one. Previously integral coordinates are unaffected, so the procedure terminates.
If one fractional coordinate remains and \(j\) coordinates equal \(h\), feasibility and the positive fractional remainder imply \(j<k\). Since \(j\) and \(k\) are integers, \(j\le k-1\). Therefore the last coordinate may range over all of \([0,h]\) while preserving feasibility. Affinity permits rounding it to an endpoint without decreasing \(Q\).
Substitution into \(Q\) gives
\(Q(h\mathbf 1_A)=h^2(3|A|-2e(A))\).
Both consequences follow with the stated constants:
The bound therefore applies to every real \(z\in P_k\), not merely rational or integral vectors.
The construction satisfies all input restrictions.
Since \(k\le n\le N\), both \(nh\le1/8\) and \(\kappa\le1/8\). The threshold estimate follows because
\[
\ell(3k-1)h^2<3k\ell h^2=3\kappa\ell h.
\]
Consequently \(0<\theta<1/4\). Thus \(\mu_p>1/4\), and \(\mu_b>3/8\); both auxiliary masses are positive. The masses sum exactly to one.
All parameters are dyadic rationals of polynomial encoding length. There are \(n+2\) explicitly represented types and one scenario of probability one. Listing even the full intensity matrix requires only polynomial space and time. The intensities are finite and nonnegative.
Distinct network blocks with identical rankings are permitted by the task. All types remain seedable, including \(p\).
The initial opposition mass is \(B=1/2+\theta\). The types ranking \(c^\star\) second are precisely the vertex types and \(b\). Hence the task’s strict victory inequality is exactly \(S(x)>\theta\). No tie convention is lost.
The auxiliary types are isolated, so their equations give \(r_b=x_b\) and \(r_p=x_p\) exactly.
On the vertex box, the diffusion map takes values in \([0,h]^V\). For fixed \(z\), its maximum-norm Lipschitz constant is at most \(3\ell h<1\): each coordinate has three incoming neighbors, and its multiplier \(h-z_v\) is at most \(h\).
The box is nonempty and complete in the maximum norm. The contraction mapping theorem therefore applies and gives a unique fixed point. Because every fixed point of the full system has the stated auxiliary coordinates, this also establishes uniqueness for the full system. Its unique fixed point is necessarily the stipulated coordinatewise least fixed point.
All bounds hold uniformly for every feasible real seed vector.
The fixed-point equations imply
\(0\le a_v\le3\ell h\) and
\(0\le\delta_v\le3\ell h^2\).
The stated integral argument correctly proves
\(\lvert1-e^{-a}-a\rvert\le a^2/2\) for every nonnegative \(a\).
The decomposition of \(\delta_v\) is exact. Its two error contributions are bounded by
\((9/2)\ell^2h^3\) and \(9\ell^2h^3\), respectively. Their sum is the claimed
\((27/2)\ell^2h^3\).
Cubic regularity gives the stated identity with \(Q(z)\): each \(z_u\) occurs three times in the linear neighbor sum, and each undirected edge contributes twice to the quadratic sum. Summing coordinate errors consequently establishes the claimed \(\mathcal E\).
The gap calculation is also correct:
\[
\frac{\mathcal E}{\ell h^2}
=\frac{27}{2}n\ell h
\le\frac{27}{256}<\frac14.
\]
The intermediate bound is loose but valid using \(n\le N\) and \(h\le1\).
In a yes-instance, fully seeding exactly \(k\) independent vertex types gives a feasible binary-rational vector. The lower error bound yields
\(S(x)\ge\theta+\ell h^2-\mathcal E>\theta\).
Hence \(\mathrm{OPT}=1\).
In a no-instance, every feasible real vector has \(z\in P_k\) and
\(\sum_vz_v+x_b\le\kappa\), regardless of seeds assigned to \(p\). Combining the rounding bound and the uniform upper error bound gives
\(S(x)\le\theta-\ell h^2+\mathcal E<\theta\).
Thus no feasible real vector wins, and \(\mathrm{OPT}=0\).
These statements establish the required separation over the full continuous feasible domain. The supremum definition causes no difficulty: the yes-instance value is attained, and every no-instance value is zero.
With one scenario, \(F(x)\in\{0,1\}\). For every fixed positive \(\alpha\), the approximation guarantee forces a winning output on a yes-instance.
The rational decoder is valid. Every no-instance output satisfies
\(Q(z)\le(3k-2)h^2\), below its acceptance threshold. Every winning output satisfies
\[
Q(z)>(3k-1)h^2-\frac{\mathcal E}{\ell}
>(3k-\tfrac54)h^2
>(3k-\tfrac32)h^2,
\]
so every yes-instance output is accepted.
A polynomial-time Turing algorithm has polynomial output length. Computing \(Q(z)\) and comparing the resulting rationals therefore takes polynomial time. No exponential evaluation or exact transcendental comparison is required.
The reduction consequently establishes NP-hardness of the requested approximation search task for every fixed \(\alpha\in(0,1]\), already with two candidates and one explicitly represented scenario.
No additional clarification or repair 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.