Answer: For every fixed \(0<\epsilon<1\), a polynomial-time \(\mathcal O(2^{(\log_2\tau)^{1-\epsilon}})\)-approximation is impossible unless \(\mathrm{NP}\subseteq\mathrm{DTIME}(n^{\operatorname{polylog}n})\).
Theorem 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe Timed Target Set Selection problem cannot be approximated within a ratio of $\mathcal{O}(2^{\log^{1-\epsilon}n})$ for any fixed $\epsilon>0$, unless $NP\subseteq DTIME(n^{polylog(n)})$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\), a symmetric nonnegative contact matrix \(A=(a_{tu})\), thresholds \(\theta_t\), and a budget \(B\), can one decide whether there is a finite timed schedule of targeted masses with total cost at most \(B\) that makes every type fully positive on a final unforced update? At time \(i\), let \(p_t(i)\) be the positive mass of type \(t\), and set \(e_t(p(i))=\frac{\sum_u a_{tu}p_u(i)}{\sum_u a_{tu}\mu_u}\). Initially \(p_t(0)=s_t(0)\); thereafter, \(p_t(i)=\mu_t\) if \(e_t(p(i-1))\ge\theta_t\), and \(p_t(i)=s_t(i)\) otherwise, with \(0\le s_t(i)\le\mu_t\). The schedule must have \(s_t(k)=0\) and \(p_t(k)=\mu_t\) for every type at its final step \(k\); its cost is \(\sum_{i=0}^k\sum_t s_t(i)\).
A society is given by its support: a list of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) counts listed types, not possible types.
Input also includes a symmetric nonnegative rational contact matrix \(A=(a_{tu})\), allowing diagonal entries, rational thresholds \(\theta_t\in[0,1]\), and a rational budget \(B\geq0\). Let \(m\) count nonzero entries with \(t\leq u\), and let \(L\) be the total input bit length.
Write \(D_t=\sum_u a_{tu}\mu_u\) and \(e_t(p)=\sum_u a_{tu}p_u/D_t\). If \(D_t=0\), require \(\theta_t=0\) and define \(e_t(p)=0\).
A schedule chooses an arbitrary finite integer horizon \(k\geq1\) and real targeted masses \(0\leq s_t(i)\leq\mu_t\), permitting repeated targeting. Initially \(p_t(0)=s_t(0)\); synchronously for \(1\leq i\leq k\), set \(p_t(i)=\mu_t\) if \(e_t(p(i-1))\geq\theta_t\), and \(p_t(i)=s_t(i)\) otherwise.
A schedule is successful if \(s_t(k)=0\) and \(p_t(k)=\mu_t\) for every type. Its cost is \(C=\sum_{i=0}^k\sum_t s_t(i)\); budget feasibility means \(C\leq B\). Let \(\mathrm{OPT}\) be the infimum cost of successful schedules; approximation concerns minimizing this cost without a prescribed budget.
For each fixed \(0<\epsilon<1\), does this mass problem admit a polynomial-time \(\mathcal{O}(2^{(\log_2\tau)^{1-\epsilon}})\)-approximation, or is such approximation impossible unless \(\mathrm{NP}\subseteq\mathrm{DTIME}(n^{\operatorname{polylog}n})\)? State running times in \(m,\tau,L\), with \(\epsilon\) fixed.
For finite simple undirected graphs with integer thresholds between zero and degree, minimizing the number of targeting occurrences has no polynomial-time \(\mathcal{O}(2^{(\log_2 n)^{1-\epsilon}})\)-approximation under that assumption, where \(n\) is the number of vertices. [Verified discrete result](https://arxiv.org/pdf/2307.09111).
No result settling this exact mass approximation problem was located in the literature search.
For every fixed \(0<\epsilon<1\), the mass problem has no polynomial-time \(\mathcal O(2^{(\log_2\tau)^{1-\epsilon}})\)-approximation unless \(\mathrm{NP}\subseteq\mathrm{DTIME}(n^{\operatorname{polylog}n})\).
The key is a deterministic rounding lemma: on instances obtained from unweighted graphs, every fractional schedule can be converted into a discrete schedule with only an \(\mathcal O(\log\tau)\) increase in cost. The construction respects dyadic masses, symmetry, zero-degree types, repeated targeting, and arbitrary finite horizons.
Lemma. Let \(V\) have \(N\geq1\) elements. Suppose \(x_v\in[0,1]\), and there are at most \(N\) constraints of the form
\(\displaystyle \sum_{v\in U_j}x_v\geq d_j,\)
where \(U_j\subseteq V\) and each \(d_j\) is a positive integer. Set
\(\displaystyle \gamma_N=4\left\lceil\log_2(4N)\right\rceil.\)
There exists \(R\subseteq V\) such that
\(\displaystyle |R\cap U_j|\geq d_j\quad\text{for every }j,\qquad |R|\leq2\gamma_N\sum_{v\in V}x_v.\)
For rational \(x_v\), such an \(R\) can be found deterministically in polynomial time.
Proof. Write \(\gamma=\gamma_N\) and \(X=\sum_vx_v\). If \(X=0\), no positive-demand constraint can be feasible, so \(R=\varnothing\) suffices.
Assume \(X>0\). Select every element of
\(\displaystyle H=\{v:x_v\geq1/\gamma\}.\)
For a constraint, subtract these selected elements from its demand:
\(\displaystyle d'_j=d_j-|H\cap U_j|.\)
Constraints with \(d'_j\leq0\) are already satisfied. For every remaining constraint,
\(\displaystyle \sum_{v\in U_j\setminus H}x_v \geq d_j-\sum_{v\in U_j\cap H}x_v \geq d_j-|H\cap U_j| =d'_j.\)
Independently select each \(v\notin H\) with probability \(q_v=\gamma x_v<1\), and let \(Z_v\) denote its selection indicator. Consider the nonnegative quantity
\(\displaystyle \Psi= \frac{|H|+\sum_{v\notin H}Z_v}{2\gamma X} +\sum_{j:d'_j>0}2^{\,d'_j-1-\sum_{v\in U_j\setminus H}Z_v}. \)
The expected numerator of the first term is at most \(\gamma X\), because
\(\displaystyle |H|+\sum_{v\notin H}q_v \leq\gamma\sum_{v\in H}x_v+\gamma\sum_{v\notin H}x_v =\gamma X.\)
For each remaining constraint, independence and \(1-z\leq e^{-z}\) give
\(\displaystyle \mathbb E\!\left[2^{\,d'_j-1-\sum_{v\in U_j\setminus H}Z_v}\right] =2^{d'_j-1}\prod_{v\in U_j\setminus H}(1-q_v/2) \leq\frac12\exp\!\left((\ln2-\gamma/2)d'_j\right). \)
Since \(\gamma\geq8\) and \(d'_j\geq1\), this is at most
\(\displaystyle \frac12e^{-\gamma/4}\leq\frac1{8N}.\)
There are at most \(N\) constraints. Consequently,
\(\displaystyle \mathbb E[\Psi]\leq\frac12+\frac18=\frac58<1.\)
Fix the indicators one at a time, always choosing a value whose conditional expectation of \(\Psi\) does not exceed the preceding conditional expectation. Such a choice exists because that preceding expectation is the probability-weighted average of the two choices.
At the resulting deterministic outcome, \(\Psi\leq5/8\). If any constraint failed, then its integer number of selected elements would be at most \(d'_j-1\), making its corresponding term in \(\Psi\) at least \(1\), a contradiction. Also, the cost term implies \(|R|\leq2\gamma X\).
For rational inputs, all conditional expectations are exactly computable rational numbers: their expressions contain products of factors \(1-q_v/2\), integer powers of \(2\), and a linear cost term. Their bit lengths are polynomial in the input encoding length. Thus conditional-expectation fixing is a deterministic polynomial-time algorithm. \(\square\)
Let \(G=(V,E)\) be a finite simple undirected graph with \(n\geq1\) vertices and integer thresholds \(r_v\in[0,d(v)]\). Let \(M(G,r)\) be its minimum number of targeting occurrences.
Choose
\(\displaystyle N=2^{\lceil\log_2n\rceil},\)
and add \(N-n\) isolated vertices with threshold zero. Call the resulting graph \(G^+\). Its discrete optimum remains \(M(G,r)\): the added vertices become positive automatically at time \(1\), and targeting them has no effect on original vertices.
Construct a mass instance \(I_G\) with one listed type per vertex of \(G^+\), using
\(\displaystyle \tau=N,\qquad \mu_v=1/N,\qquad a_{vu}=\begin{cases}1,&\{v,u\}\in E(G^+),\\0,&\text{otherwise},\end{cases}\)
and
\(\displaystyle \theta_v=\begin{cases}r_v/d(v),&d(v)>0,\\0,&d(v)=0.\end{cases} \)
Set the unused budget parameter to \(B=1\).
All masses are positive dyadic rationals and sum to \(1\). The matrix is symmetric and nonnegative. For an isolated type, \(D_v=0\) and \(\theta_v=0\), as required.
Normalize any mass schedule by defining
\(\displaystyle x_v(i)=Ns_v(i),\qquad y_v(i)=Np_v(i).\)
For a nonisolated vertex,
\(\displaystyle D_v=d(v)/N,\qquad e_v(p(i))=\frac{\sum_{u\in N(v)}y_u(i)}{d(v)}.\)
Therefore its autonomous activation condition is exactly
\(\displaystyle \sum_{u\in N(v)}y_u(i)\geq r_v.\)
For isolated vertices, the same condition holds because both sides are zero.
Every discrete successful schedule gives a mass successful schedule by targeting mass \(1/N\) at each discrete targeting occurrence. Hence
\(\displaystyle \mathrm{OPT}(I_G)\leq\frac{M(G,r)}N.\)
This direction alone would not transfer hardness; fractional schedules could be cheaper. The next step controls that possibility.
Proposition. Every successful mass schedule for \(I_G\), of cost \(C\) and finite horizon \(k\), yields a successful discrete schedule on \(G^+\) with at most \(2\gamma_NNC\) targeting occurrences.
Proof. For each time \(i\), define
\(\displaystyle P_i=\{v:y_v(i)=1\},\qquad T_i=\{v:x_v(i)=1\}.\)
Let \(Q_0=\varnothing\), and for \(i\geq1\) let
\(\displaystyle Q_i=\left\{v:\sum_{u\in N(v)}y_u(i-1)\geq r_v\right\}.\)
The given update rule implies
\(\displaystyle P_i=Q_i\cup T_i.\)
Moreover, if \(v\notin P_i\), then \(v\) was not activated autonomously, so
\(\displaystyle y_v(i)=x_v(i).\)
Fix \(i<k\). For each \(v\in Q_{i+1}\), the preceding state satisfies
\(\displaystyle |N(v)\cap P_i|+\sum_{u\in N(v)\setminus P_i}x_u(i)\geq r_v. \)
Whenever the integer residual demand
\(\displaystyle d_{v,i}=r_v-|N(v)\cap P_i|\)
is positive, apply the covering lemma to the variables indexed by \(V(G^+)\setminus P_i\). There are at most \(N\) constraints. It produces \(R_i\subseteq V(G^+)\setminus P_i\) satisfying
\(\displaystyle |R_i\cap N(v)|\geq d_{v,i},\qquad |R_i|\leq2\gamma_N\sum_{u\notin P_i}x_u(i). \)
Use the discrete targeting sets
\(\displaystyle S_i=T_i\cup R_i\quad(0\leq i<k),\qquad S_k=\varnothing.\)
Let \(Z_i\) be the actual set of positive vertices under this discrete schedule. We prove that \(P_i\subseteq Z_i\).
Initially, \(P_0=T_0\subseteq S_0=Z_0\). Suppose \(P_i\subseteq Z_i\). Since \(R_i\subseteq S_i\subseteq Z_i\), and \(R_i\cap P_i=\varnothing\), every \(v\in Q_{i+1}\) has at least \(r_v\) neighbors in \(Z_i\): the neighbors in \(P_i\) suffice when the residual demand is nonpositive, and the covering constraint supplies the remainder otherwise. Thus every vertex in \(Q_{i+1}\) activates autonomously in the discrete process. Adding \(T_{i+1}\) establishes \(P_{i+1}\subseteq Z_{i+1}\).
At the final time, success of the mass schedule and \(x_v(k)=0\) imply \(Q_k=V(G^+)\). Therefore every vertex activates autonomously at time \(k\), with \(S_k=\varnothing\). The discrete schedule is successful.
Finally, \(T_i\) and \(R_i\) are disjoint, and \(x_v(i)=1\) on \(T_i\). Therefore
\(\displaystyle |S_i| \leq |T_i|+2\gamma_N\sum_{u\notin P_i}x_u(i) \leq2\gamma_N\sum_u x_u(i). \)
Summing over \(i<k\), and using \(s_v(k)=0\), gives
\(\displaystyle \sum_{i=0}^k|S_i|\leq2\gamma_NNC.\)
\(\square\)
The existence argument applies to real targeting masses; the deterministic algorithm applies to rationally encoded schedules. Taking the infimum over all successful mass schedules now gives the useful two-sided comparison
\(\displaystyle \frac{M(G,r)}{2\gamma_NN} \leq\mathrm{OPT}(I_G) \leq\frac{M(G,r)}N. \)
No assumption that the infimum is attained is needed.
The embedding has \(\tau=N<2n\) and exactly \(m=|E|\) nonzero upper-triangular contact entries. Its encoding length is \(L=\mathcal O((m+\tau)\log\tau)\) under sparse encoding; a dense matrix encoding adds \(\mathcal O(\tau^2)\) bits. Construction takes polynomial time in \(m,\tau,L\).
For a rational schedule with encoding length \(S\) and explicitly listed horizon \(k\), simulation and rounding use
\(\displaystyle \mathcal O((k+1)\tau(m+\tau))\)
rational arithmetic operations, with operand bit lengths polynomial in \(L+S+\tau\). To obtain this bound, at each time one may recompute both conditional expectations for each of at most \(\tau\) variables; all constraint incidences together number at most \(2m\).
A polynomial horizon need not be assumed. The following argument also handles schedules represented by nonzero targeting times written in binary.
During an interval without targeting, the mass state becomes binary after its first update. Subsequent updates are the discrete map
\(\displaystyle F(b)_v=\mathbf1\!\left\{\sum_{u\in N(v)}b_u\geq r_v\right\}.\)
For binary vectors \(b,c\), define the symmetric energy
\(\displaystyle E(b,c)= -\sum_{u,v}a_{uv}b_uc_v +\sum_v(r_v-\tfrac12)(b_v+c_v). \)
For fixed \(b\), the coefficient of \(c_v\) is
\(\displaystyle r_v-\tfrac12-\sum_{u\in N(v)}b_u.\)
It is a nonzero half-integer. Consequently, \(F(b)\) is the unique minimizer of \(E(b,c)\) over binary \(c\). Along an uncontrolled trajectory, whenever \(b_{i+1}\ne b_{i-1}\),
\(\displaystyle E(b_i,b_{i+1}) \leq E(b_i,b_{i-1})-\tfrac12 =E(b_{i-1},b_i)-\tfrac12. \)
The energy lies between \(-2m-\tau\) and \(4m\). Thus there can be at most \(12m+2\tau\) consecutive strict decreases. Once \(b_{i+1}=b_{i-1}\), determinism makes the trajectory periodic with period dividing two.
It follows that every interval without targeting can be shortened to \(\mathcal O(m+\tau)\) steps while preserving its endpoint state: retain the transient and then preserve the parity of the remaining period-two segment. This preserves the state entering the next targeting step, and preserves final success.
If \(z\) times have nonzero targeting, the shortened horizon is therefore
\(\displaystyle k=\mathcal O((z+1)(m+\tau)).\)
Since \(z\leq S\), compression and rounding take
\(\displaystyle \mathcal O((S+1)\tau(m+\tau)^2) \)
rational arithmetic operations, with polynomial bit complexity in \(L+S+\tau\).
Accordingly, if an alleged mass approximation algorithm runs in time \(T_\epsilon(m,\tau,L)\), the complete discrete reduction runs in
\(\displaystyle T_\epsilon(m,\tau,L)+ \operatorname{poly}\!\bigl(m,\tau,L,T_\epsilon(m,\tau,L)\bigr). \)
For fixed \(\epsilon\), this is polynomial whenever \(T_\epsilon\) is polynomial.
Assume a polynomial-time mass approximation algorithm with guarantee
\(\displaystyle C\leq K_\epsilon\,2^{(\log_2\tau)^{1-\epsilon}}\mathrm{OPT}\)
for some constant \(K_\epsilon\). Apply it to \(I_G\), and then round its output. The resulting discrete schedule has cost at most
\(\displaystyle 2\gamma_NN C \leq 2\gamma_NK_\epsilon\, 2^{(\log_2N)^{1-\epsilon}}M(G,r). \)
Its approximation ratio is therefore
\(\displaystyle \mathcal O\!\left(\log n\;2^{(\log_2N)^{1-\epsilon}}\right). \)
Set \(\delta=\epsilon/2\). Because \(\log_2N\leq\log_2n+1\), this ratio is
\(\displaystyle \mathcal O\!\left(2^{(\log_2n)^{1-\delta}}\right).\)
To verify the absorption explicitly, put \(h=\log_2n\). The logarithm of the preceding ratio is at most
\(\displaystyle \mathcal O(1)+\log_2h+(h+1)^{1-\epsilon}.\)
Dividing this expression by \(h^{1-\epsilon/2}\) gives a quantity tending to zero. Thus the asserted bound holds for all sufficiently large \(n\), with the remaining finite range absorbed into its constant.
The supplied discrete hardness theorem excludes precisely such a polynomial-time approximation for the fixed parameter \(\delta>0\), unless \(\mathrm{NP}\subseteq\mathrm{DTIME}(n^{\operatorname{polylog}n})\). Its targeting and terminal-success conventions match those used above. See [Definition 1 and Theorem 6 of the verified discrete result](https://arxiv.org/pdf/2307.09111).
Hence the proposed mass approximation is impossible under the stated assumption, even with uniform dyadic masses and a contact matrix consisting only of the adjacency matrix of a simple graph.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed approximation hardness under the standard convention that a polynomial-time approximation algorithm outputs a rationally encoded schedule. I found three minor specification issues and no substantive mathematical error.
1. Deterministic covering lemma
The probabilistic argument and its derandomization are correct.
For each unsatisfied constraint, the residual demand \(d'_j\) is a positive integer. Since \(x_v\leq1\), subtracting the selected elements leaves fractional weight at least \(d'_j\), as claimed.
The expected cost contribution is at most \(1/2\). For each residual constraint, independence gives the displayed product, and its exponential bound follows from
\[
\sum_{v\in U_j\setminus H}q_v\geq\gamma d'_j.
\]
The constants also check: for \(\gamma\geq8\), one has \(\ln2-\gamma/2\leq-\gamma/4\), and the stated choice of \(\gamma\) ensures
\[
\frac12e^{-\gamma/4}\leq\frac1{8N}.
\]
Thus the total expectation is at most \(5/8\).
Conditional-expectation fixing is valid. A failed constraint contributes at least \(1\), contradicting the final bound on \(\Psi\). The cost term gives the claimed cardinality bound. For rational inputs, the expressions can indeed be evaluated exactly with polynomial bit lengths.
The case \(X=0\) is handled correctly: under the lemma’s feasibility hypothesis, there cannot be any positive-demand constraint.
2. Graph embedding
The embedding is correct.
Padding to a power of two gives positive dyadic masses and \(n\leq N<2n\). Added isolated vertices with threshold zero activate automatically at time \(1\), cannot affect original vertices, and do not change the discrete optimum.
For nonisolated vertices, the normalization correctly produces
\[
D_v=\frac{d(v)}N,\qquad
e_v(p(i))=\frac{\sum_{u\in N(v)}y_u(i)}{d(v)}.
\]
Consequently, the autonomous activation condition becomes precisely the discrete integer-threshold condition. Isolated vertices satisfy the special rule in the task.
Converting discrete targeting occurrences to full-mass targeting preserves the dynamics and terminal success. Therefore the upper comparison
\[
\mathrm{OPT}(I_G)\leq\frac{M(G,r)}N
\]
is justified. Setting the unused budget to \(1\) is permissible because the target question concerns cost approximation without a prescribed budget.
3. Rounding an entire schedule
The state identities and induction are correct. At time zero, \(P_0=T_0\). At later times, full positivity is equivalent to autonomous activation or full targeting. Outside \(P_i\), the state equals the targeted fraction.
The residual covering constraints therefore accurately describe the additional neighbors needed to preserve every autonomous activation in \(Q_{i+1}\).
There is one minor formal issue: the lemma is stated with at most as many constraints as elements in its universe. The proposition applies it to \(V(G^+)\setminus P_i\), whose cardinality can be smaller than the number of constraints, while continuing to use the parameter \(N\). The proof of the lemma depends on the original upper bound \(N\), so this is a parameter-specification omission rather than a substantive failure.
Minimum clarification: State explicitly how the application retains an ambient universe of size \(N\), or state the lemma with a separate upper-bound parameter for the universe size and number of constraints. Address the empty remaining-variable case explicitly.
Subject to that clarification, the induction verifies \(P_i\subseteq Z_i\). The final transition is valid because mass success and zero final targeting imply \(Q_k=V(G^+)\); no final targeting is required.
The cost calculation is also correct. \(T_i\) and \(R_i\) are disjoint, each member of \(T_i\) contributes one unit of normalized targeting, and the remaining rounded cost is bounded by the lemma.
The lower comparison follows for every successful schedule before taking an infimum. Thus no attainment assumption is being used.
4. Horizon compression and running time
The energy argument is valid on the constructed graph instances.
For fixed \(b\), every coefficient of \(c_v\) is a nonzero half-integer. Its sign selects exactly \(F(b)_v\), making \(F(b)\) the unique minimizer. Whenever consecutive alternating states differ, the energy decreases by at least \(1/2\). Symmetry justifies exchanging the two arguments.
The claimed range
\[
-2m-\tau\leq E(b,c)\leq4m
\]
is valid, including isolated zero-threshold vertices. Its width is \(6m+\tau\), so the bound of \(12m+2\tau\) strict decreases checks.
Once \(b_{i+1}=b_{i-1}\), determinism gives period dividing two. Together with the first untargeted update producing a binary state, this justifies shortening untargeted intervals while preserving their endpoint states. The resulting horizon bound is sufficient even when original targeting times are written in binary.
The arithmetic-operation bounds are consistent with recomputing conditional expectations over at most \(\tau\) variables and at most \(2m\) constraint incidences. Exact rational arithmetic has polynomial bit complexity in the stated encoding parameters.
Two minor specifications remain:
Neither issue requires new mathematics under the intended computational model.
5. Discrete hardness theorem and approximation transfer
The external theorem is applicable. The cited paper considers simple undirected graphs with integer thresholds between zero and degree. Its Definition 1 permits repeated targeting, counts targeting occurrences, and requires an empty final targeting set with every vertex autonomously positive. Theorem 6 states the corresponding subexponential-factor approximation hardness under the assumption used here. These conventions match the reduction. [Definition 1 and Theorem 6](https://arxiv.org/pdf/2307.09111)
The transferred approximation factor is correctly bounded by
\[
2\gamma_NK_\epsilon\,2^{(\log_2N)^{1-\epsilon}}.
\]
Since \(\gamma_N=\mathcal O(\log n)\) asymptotically and \(\log_2N\leq\log_2n+1\), choosing \(\delta=\epsilon/2\) absorbs the logarithmic loss. The displayed limiting calculation is correct because \(0<\epsilon<1\).
The resulting discrete algorithm runs in polynomial time whenever the alleged mass algorithm does. It contradicts the supplied discrete theorem unless the stated complexity-class inclusion holds.
The hardness conclusion therefore survives all identified issues; the write-up needs only the specified expositional clarifications.
⟨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.