Answer: \(\mathsf{NP}\)-complete, hence \(\mathsf{NP}\)-hard.
Theorem 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate\twoTSS is \Whard when parameterized by the treedepth, the feedback vertex number, the 4-path vertex cover number of the input graph and the budget $B$ combined, even if any successful activation process is guaranteed to stabilize in~$\fin = 4$ rounds and $f_1(v) \le f_2(v)$ for every vertex~$v$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many roles \(T\), rational role masses \(\mu_{t,q}\) for each initial opinion state \(q\subseteq\{a,b\}\), a symmetric nonnegative rational exposure matrix \(K\), rational thresholds \(\theta_{t,1},\theta_{t,2}\), and a four-round horizon, choose rational seed masses \(x_{t,q,r}\ge 0\), where \(r\subseteq\{a,b\}\setminus q\) and \(\sum_r x_{t,q,r}=\mu_{t,q}\). At each round, role \(t\) receives opinion-\(c\) exposure \(E^i_{t,c}=\sum_{u\in T}K_{tu}M^i_{u,c}\), where \(M^i_{u,c}\) is the mass of role \(u\) holding \(c\); unopinionated agents adopt \(c\) at threshold \(\theta_{t,1}\), and agents already holding the other opinion adopt \(c\) at threshold \(\theta_{t,2}\). Minimize \(\sum_{t,q,r}|r|x_{t,q,r}\) subject to stabilization by round \(4\) and zero mass holding exactly one opinion.
A society is given by its support: the list of the \(\tau\) types \((t,q)\) with positive mass, each mass \(\mu_{t,q}\) a binary rational; \(\tau\) is the support size, not the number of possible types. Here \(T\) is a nonempty set of roles, \(m=|T|\), \(q\subseteq\{a,b\}\), omitted masses are zero, and \(\sum_{t,q}\mu_{t,q}=1\).
Input also includes a symmetric matrix \(K\in\mathbb Q_{\ge0}^{T\times T}\), thresholds \(0\le\theta_{t,1}\le\theta_{t,2}\) in \(\mathbb Q\), and a binary rational budget \(B>0\). Diagonal entries of \(K\) represent exposure within a role and may be positive. Let \(L\) be the total input bit length.
Choose rational masses \(x_{t,q,r}\ge0\) for every \(r\subseteq\{a,b\}\setminus q\), including \(r=\varnothing\), with \(\sum_r x_{t,q,r}=\mu_{t,q}\). This assigns mass \(x_{t,q,r}\) initial state \(q\cup r\), at cost \(\sum_{t,q,r}|r|x_{t,q,r}\); seeding occurs only at initialization.
Let \(y^i_{t,s}\) be the mass in role \(t\) holding exactly state \(s\) after round \(i\), so \(y^0_{t,s}=\sum_{q,r:q\cup r=s}x_{t,q,r}\). Define \(M^i_{t,c}=\sum_{s:c\in s}y^i_{t,s}\) and \(E^i_{t,c}=\sum_u K_{tu}M^i_{u,c}\).
Updates are deterministic and synchronous: each entire mass \(y^i_{t,s}\) retains its opinions and adds each missing \(c\) when \(E^i_{t,c}\ge\theta_{t,1}\) if \(s=\varnothing\), or \(E^i_{t,c}\ge\theta_{t,2}\) otherwise. Both opinions can be acquired simultaneously from the empty state, using the first threshold for both; equality triggers adoption.
A feasible allocation has cost at most \(B\), satisfies \(y^4_{t,s}=y^5_{t,s}\) for every role and state, and satisfies \(y^4_{t,\{a\}}=y^4_{t,\{b\}}=0\) for every role.
Is deciding whether a feasible rational allocation exists in \(\mathsf P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathsf{NP}\)-hard?
Discrete two-opinion target set selection is \(\mathsf{NP}\)-hard; it is also \(\mathsf{W[1]}\)-hard for budget, treedepth, feedback vertex number, and four-path vertex cover number combined, even with ordered thresholds and successful processes stabilizing within four rounds. [Discrete results](https://arxiv.org/html/2105.10184v3)
No complexity result for this exact mass problem was located in the literature search.
The decision problem is \(\mathsf{NP}\)-complete. Hardness holds even when every role has exactly one supported type, initially holding \(\{a\}\), and \(\theta_{t,1}=\theta_{t,2}\) for every role.
The reduction below explicitly allows arbitrary fractional seeding. Positive diagonal entries amplify sufficiently seeded roles, while quantitative bounds prevent smaller fractional seeds from bypassing the reduction.
We use the standard \(\mathsf{NP}\)-completeness of Vertex Cover: given a simple undirected graph \(G=(V,E)\) and an integer \(k\), decide whether some \(C\subseteq V\) with \(|C|\le k\) meets every edge. See [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Write \(n=|V|\) and \(h=|E|\). We may restrict to \(h\ge1\) and \(1\le k<n\). The excluded cases are immediately decidable and can be replaced by fixed yes or no instances satisfying these restrictions.
Introduce a selector role \(s_v\) for every \(v\in V\), an edge role \(d_e\) for every \(e\in E\), and one completion role \(z\). Thus \(m=n+h+1\).
Define
\(W=4(k+1),\qquad \eta=\dfrac{1}{16hW(k+1)},\qquad R_0=64hnW(k+1)+16(k+1)^2.\)
Let \(N\) be the smallest power of two satisfying \(N\ge(n+h)W+R_0\), and set
\(R=N-(n+h)W.\)
In particular, \(R\ge R_0\). Assign the supported masses
\(\mu_{s_v,\{a\}}=\dfrac{W}{N},\qquad \mu_{d_e,\{a\}}=\dfrac{W}{N},\qquad \mu_{z,\{a\}}=\dfrac{R}{N}.\)
All other masses are zero. These masses sum to one, are dyadic rationals, and give \(\tau=m\).
Define the symmetric exposure matrix by the following entries:
All unspecified entries are zero.
For convenience, define unnormalized thresholds
\(\Theta_{s_v}=1,\qquad \Theta_{d_e}=\dfrac{\eta W}{2},\qquad \Theta_z=\eta\left(h-\dfrac12\right)W.\)
The actual thresholds and budget are
\(\theta_{t,1}=\theta_{t,2}=\dfrac{\Theta_t}{N},\qquad B=\dfrac{k}{N}.\)
Every threshold is positive, the ordered-threshold requirement holds, and \(B>0\).
All constructed numbers have bit length polynomial in the Vertex Cover input length. The number of roles and the explicitly written matrix size are also polynomial. Hence this is a polynomial-time construction.
Every agent initially holds \(a\), so the only seeding choice is whether to add \(b\). Every state throughout the process is therefore either \(\{a\}\) or \(\{a,b\}\).
Let \(p_t\) be the unnormalized mass seeded with \(b\) in role \(t\). The budget condition becomes
\(p_t\ge0,\qquad \sum_{t\in T}p_t\le k.\)
Let \(w_t=W\) for selector and edge roles, and \(w_z=R\). Both \(W>k\) and \(R>k\), so no role can be fully seeded.
Define the unnormalized \(b\)-mass and exposure by
\(A_t^i=N M_{t,b}^i,\qquad F_t^i=\sum_{u\in T}K_{tu}A_u^i.\)
Adoption occurs exactly when \(F_t^i\ge\Theta_t\). Before a role’s unseeded mass adopts \(b\), its \(b\)-mass remains \(p_t\); afterward, its \(b\)-mass is \(w_t\). This follows because all its remaining mass has the same state \(\{a\}\) and undergoes the same deterministic update.
We say that a role activates in the round when this remaining mass adopts \(b\).
Two bounds will control fractional seeding. First,
\(h\eta W=\dfrac{1}{16(k+1)},\qquad \dfrac{k}{R}\le\dfrac{k}{16(k+1)^2}<\dfrac{1}{16(k+1)}.\)
Consequently,
\(h\eta W+\dfrac{k}{R}<\dfrac{1}{8(k+1)}.\) \[\tag{1}\]
Second,
\(\dfrac{nW}{R}\le\dfrac{1}{64h(k+1)}=\dfrac{\eta W}{4}.\) \[\tag{2}\]
Suppose \(C\subseteq V\) is a vertex cover with \(|C|\le k\). Seed unnormalized mass one with \(b\) in each selector \(s_v\) for \(v\in C\), and seed nothing elsewhere.
The actual cost is \(|C|/N\le B\).
The following statements concern adoption by each indicated round:
Thus all mass holds \(\{a,b\}\) by round four. There are no singleton states, and no further change is possible in round five. The allocation is feasible.
Consider any feasible allocation, allowing arbitrary rational fractional seeds.
Because every role always holds \(a\), the requirement \(y^4_{t,\{a\}}=0\) forces every role to activate by round four. Let \(j\in\{1,2,3,4\}\) be the activation round of \(z\).
Define
\(S=\{v\in V:s_v\text{ activates strictly before round }j\}.\)
We prove that \(|S|\le k\) and that \(S\) covers every edge.
Take \(v\in S\), and suppose its selector activates in round \(\ell<j\). In the preceding exposure round, \(z\) has not activated, so its \(b\)-mass is \(p_z\). The selector’s own \(b\)-mass is still \(p_{s_v}\), and every incident edge role has \(b\)-mass at most \(W\).
Its successful threshold comparison therefore implies
\(1\le p_{s_v}+h\eta W+\dfrac{p_z}{R} \le p_{s_v}+h\eta W+\dfrac{k}{R}.\)
Using (1),
\(p_{s_v}>1-\dfrac{1}{8(k+1)}.\)
If \(|S|\ge k+1\), then
\(\displaystyle \sum_{t\in T}p_t \ge\sum_{v\in S}p_{s_v} >(k+1)\left(1-\dfrac{1}{8(k+1)}\right) =k+\dfrac78, \)
contradicting the budget. Hence \(|S|\le k\).
The successful comparison activating \(z\) uses exposures from round \(j-1\).
Suppose some edge role has not activated by that round. Its \(b\)-mass is its initial seed, which is at most \(k\). Each other edge role has \(b\)-mass at most \(W\), and each selector also has \(b\)-mass at most \(W\). Therefore, by (2),
\(\displaystyle F_z^{j-1} \le \eta\bigl((h-1)W+k\bigr)+\dfrac{nW}{R} \le \eta\left((h-1)W+k+\dfrac W4\right). \)
But \(W/4=k+1>k\), so
\(\displaystyle (h-1)W+k+\dfrac W4 < \left(h-\dfrac12\right)W. \)
Thus \(F_z^{j-1}<\Theta_z\), contradicting activation of \(z\) in round \(j\).
Every edge role must consequently activate strictly before round \(j\). This step uses synchronous updating: activation of \(z\) cannot depend on edge activations in the same round.
Take an edge \(e=\{u,v\}\), and let \(\ell<j\) be its edge role’s activation round.
If neither endpoint selector had activated by round \(\ell-1\), then their \(b\)-masses would still be \(p_{s_u}\) and \(p_{s_v}\). The completion role would also still have \(b\)-mass \(p_z\). These are the edge role’s only neighbors, so
\(\displaystyle F_{d_e}^{\ell-1} =\eta(p_{s_u}+p_{s_v}+p_z) \le\eta k <\dfrac{\eta W}{2} =\Theta_{d_e}. \)
This contradicts its activation.
At least one endpoint selector therefore activates before the edge role, hence before \(z\). That endpoint belongs to \(S\). Since \(e\) was arbitrary, \(S\) is a vertex cover of size at most \(k\).
Together with completeness, this proves \(\mathsf{NP}\)-hardness.
It remains to justify polynomial-size rational certificates; rational feasibility alone does not establish this.
Consider a feasible allocation and record, for every round \(i\in\{0,1,2,3,4\}\), role \(t\), opinion \(c\), and threshold index \(j\in\{1,2\}\), whether
\(E^i_{t,c}\ge\theta_{t,j}.\)
There are \(20m\) such Boolean comparisons.
For a fixed comparison pattern, every state’s destination in each synchronous update is fixed. The constraints then form a rational linear system:
This system has polynomially many variables and constraints: at most \(4\tau\) allocation variables and \(24m\) state-mass variables. Its coefficients have polynomial bit length.
Introduce a variable \(\delta\), with \(0\le\delta\le1\), and replace every failed comparison by
\(E^i_{t,c}\le\theta_{t,j}-\delta.\)
Also bound every allocation and state-mass variable between zero and one; these bounds hold for every genuine trajectory.
The original feasible allocation realizes this augmented system with some \(\delta>0\): take the minimum of one and the finitely many positive failure margins. If there are no failed comparisons, take \(\delta=1\).
The augmented feasible region is a nonempty bounded rational polytope. Maximizing \(\delta\) therefore has a vertex optimum with positive objective value. Such a vertex has polynomial bit length: after clearing denominators, its coordinates are determined by a square nonsingular subsystem of active constraints; Cramer’s rule and the determinant bound give polynomial-size numerators and denominators.
The allocation coordinates of this vertex satisfy every original strict comparison because \(\delta>0\). They therefore produce the recorded trajectory and form a polynomial-size feasible rational allocation.
A verifier can check such an allocation by exact rational arithmetic, simulate five synchronous rounds, and check the budget and terminal conditions, all in polynomial time. Thus the problem belongs to \(\mathsf{NP}\).
The exact mass-allocation problem is \(\mathsf{NP}\)-complete, even with \(\tau=m\), only initial type \(\{a\}\), and equal first and second thresholds. Consequently, a running time polynomial in \(m,\tau,L\) would imply \(\mathsf P=\mathsf{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The reduction establishes \(\mathsf{NP}\)-hardness for the exact rational mass problem, including arbitrary fractional seeding, and the certificate argument establishes membership in \(\mathsf{NP}\). I found no major or minor issues.
The invoked theorem is the standard \(\mathsf{NP}\)-completeness of Vertex Cover on simple undirected graphs, with the decision condition stated correctly. The supplied citation identifies [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Restricting to \(h\ge1\) and \(1\le k<n\) is legitimate: all excluded cases are immediately decidable, and fixed yes and no instances exist within the restricted family. Thus this restriction preserves the reduction’s validity.
All parameters are well-defined and positive under those restrictions. The choice of \(N\) guarantees \(R\ge R_0>0\).
There are exactly \(n+h+1\) roles, each with one positive supported type. The total supported mass is
\[
\frac{(n+h)W+R}{N}=1.
\]
Since \(N\) is a power of two, the masses and budget have the required binary rational representation.
The matrix is symmetric and nonnegative. Its positive selector diagonal entries are expressly permitted by the task. Both thresholds coincide in every role, and all are positive.
The parameters have polynomial bit length, and writing the full matrix requires polynomial space and time. The construction therefore satisfies the stated encoding requirements, with \(\tau=m\).
Every supported type initially holds \(a\), and its only possible additional seed is \(b\). Consequently, the only states appearing are \(\{a\}\) and \(\{a,b\}\).
The normalization is consistent: actual seed cost is \(\sum_t p_t/N\), so the budget condition becomes \(\sum_t p_t\le k\). Multiplying the exposure comparison by \(N\) gives exactly \(F_t^i\ge\Theta_t\).
Both \(W>k\) and \(R>k\), so every role has strictly positive unseeded mass. Within a role, all unseeded mass has the same state and faces the same comparison. Therefore its \(b\)-mass remains \(p_t\) until one activation event changes it to \(w_t\). This correctly captures the deterministic mass dynamics without imposing integral seeding.
Both displayed bounds are correct. In particular,
\[
h\eta W=\frac{1}{16(k+1)}
\]
and the lower bound on \(R\) gives
\[
\frac{k}{R}\le\frac{k}{16(k+1)^2}<\frac{1}{16(k+1)}.
\]
Their sum is therefore strictly below \(1/[8(k+1)]\), as required.
The other part of the lower bound on \(R\) gives
\[
\frac{nW}{R}\le\frac{1}{64h(k+1)}=\frac{\eta W}{4}.
\]
The constants and strictness used later are valid throughout the restricted input range.
Seeding unnormalized mass one at each selected selector is permitted because \(W>1\), and its cost is \(|C|/N\le B\).
Each round uses only masses available after the preceding round:
Equality is used correctly for selector activation. Earlier activation of any role does not invalidate these “by round” claims because opinions are retained and all matrix entries are nonnegative.
Once all mass holds \(\{a,b\}\), the singleton conditions hold and round five cannot change any state. Thus the constructed allocation satisfies both terminal requirements.
Feasibility forces every role to activate by round four: each has positive unseeded mass, and any role that had not activated would retain positive mass in \(\{a\}\). Therefore the completion role’s activation round \(j\) exists in the specified range.
For a selector activating in round \(\ell<j\), the exposure at round \(\ell-1\) contains its own seed \(p_{s_v}\), at most \(h\eta W\) from incident edges, and \(p_z/R\) from the still-inactive completion role. These are all its possible contributions.
The resulting lower bound
\[
p_{s_v}>1-\frac{1}{8(k+1)}
\]
is correct. If at least \(k+1\) such selectors existed, their seeds alone would total more than \(k+7/8\), contradicting the budget. Hence \(|S|\le k\).
The successful comparison for completion-role activation uses round \(j-1\). If an edge role remains inactive then, its mass is at most \(k\), while all other edge and selector masses are bounded by \(W\).
The stated exposure bound includes every possible contribution to the completion role. Its diagonal entry is zero, so there is no omitted self-contribution.
The crucial comparison is strict because
\[
\left(h-\frac12\right)W-
\left((h-1)W+k+\frac W4\right)
=\frac W4-k=1>0.
\]
Thus the hypothetical inactive edge would prevent completion-role activation.
The argument correctly excludes dependence on edge activation in the same round, as required by synchronous updating. It also handles the possible boundary case \(j=1\): the resulting contradiction rules that case out.
An edge role has exactly the two endpoint selectors and the completion role as neighbors, with weight \(\eta\) for each. Its diagonal entry is zero.
Before its activation in round \(\ell<j\), the completion role remains inactive. If both endpoint selectors also remain inactive through round \(\ell-1\), the exposure is exactly the stated sum of their three initial seeds.
Those seeds total at most \(k\), and
\[
\eta k<\frac{\eta W}{2}.
\]
Therefore such an edge role could not activate. At least one endpoint selector must activate strictly earlier, and hence belong to \(S\).
This establishes a vertex cover of size at most \(k\) for every feasible allocation. Arbitrary fractional seeds are fully covered by the soundness argument.
Recording comparisons for five exposure rounds, two opinions, and two thresholds gives exactly \(20m\) Boolean comparisons. The round indices correctly cover the updates producing rounds one through five.
Fixing these comparisons fixes every state’s destination. The resulting initialization, update, budget, and terminal constraints are linear. The claimed variable bounds—at most \(4\tau\) allocation variables and \(24m\) state-mass variables—are correct.
Failed comparisons must remain strict because equality triggers adoption. The common slack variable \(\delta\) handles this correctly: finitely many failed comparisons in a feasible trajectory have a positive minimum margin, and the no-failure case permits \(\delta=1\).
Adding bounds between zero and one preserves every genuine trajectory. The augmented feasible region is a nonempty bounded rational polytope. Therefore maximizing \(\delta\) attains a vertex optimum, and its value is positive because a feasible point with positive \(\delta\) already exists.
The invoked vertex-coordinate argument applies: a vertex admits a full-rank subsystem of active constraints, and the polynomial dimension and coefficient bit lengths give polynomial coordinate bit lengths through Cramer’s rule and determinant bounds. This remains valid if the polytope has lower affine dimension.
The resulting allocation preserves all recorded comparisons, including strict failures, and thus realizes the required trajectory. Exact simulation of five rounds and verification of the budget and terminal conditions take polynomial time.
The claimed \(\mathsf{NP}\)-completeness follows. No additional clarification, missing lemma, 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.