Answer: —
Theorem 1 (SDP) — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe final cascade size distribution $p_C(\rho)$ of an ICM $(\mathbf{p}, \mathbf{W})$ on a tree $G$ with root $r$ and $N$ nodes is given as output of the following message passing algorithm. Starting in the leaves, each node $n$ sends the functions $p_{B_n}(a)$, $p_{A^{0}_n}(a)$, and $p_{A^{\Sigma}_n (a)}$ for $a = 0, ..., N$ as messages to its parent $p$.
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\) summing to one, bounded type-specific contact-stub counts, rational transmission probabilities \(w_{tu}\), and rational seed intensities \(\lambda_t\), take populations with type proportions tending to \(\mu\). Pair compatible stubs uniformly, activate each type-\(t\) agent initially with probability \(\lambda_t/n\), and run the Independent Cascade Model with transmission probability \(w_{tu}\) on type-\(t\)-to-type-\(u\) contacts. Compute the exact limiting distribution of the final infected fraction \(\rho_n\), and determine the complexity in \(|T|\), the parameter bit length, and the degree bound.
A society is given by its support \(T\): the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type \(t\) has integer stub counts \(d_{tu}\geq0\) specifying contacts with type \(u\), with \(\sum_u d_{tu}\leq D\) and \(\mu_t d_{tu}=\mu_u d_{ut}\). Set \(m=|\{(t,u):d_{tu}>0\}|\). Transmission probabilities \(w_{tu}\in[0,1]\) and seed intensities \(\lambda_t\geq0\) are binary rationals; \(L\) is the total input bit length.
For population sizes \(n\) making all \(n\mu_t\) integral and each within-type stub pool even, use exactly \(n\mu_t\) agents of type \(t\). Match the reciprocal stub pools uniformly, conditioning on a simple undirected contact graph. Restrict to inputs for which such graphs exist for all sufficiently large admissible \(n\).
Independently seed each type-\(t\) agent with probability \(\lambda_t/n\), for sufficiently large \(n\), and run the Independent Cascade Model with independent directed transmission trials of probability \(w_{tu}\). Let \(\rho_n\) be the final infected fraction; its law averages over graph construction, seeds, and transmissions.
For exact computation, access a limiting law \(\nu\) through rational CDF cuts: given binary rationals \(x,q\in[0,1]\), decide whether \(\nu([0,x])\geq q\), including equality. Include their encoding in \(L\).
Does \(\rho_n\) have a weak limiting law for every admissible input, and is the exact limiting-distribution problem, in this CDF-cut formulation, in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L,D\).
For finite trees, SDP computes the exact Independent Cascade cascade-size distribution using \(O(N^2)\) arithmetic operations ([Burkholz–Quackenbush](https://ojs.aaai.org/index.php/AAAI/article/download/16844/16651)).
For bounded-degree configuration-model SIR epidemics, final-size central limit theorems cover fixed initial infective counts conditional on a large outbreak; this does not establish the exact CDF-cut complexity above ([Ball](https://arxiv.org/abs/1812.03105)).
The exact CDF-cut problem is $\mathrm{NP}$-hard already on admissible inputs with $D=3$ whose limiting laws exist.
I also prove two convergence results:
Universal convergence remains unresolved here. In particular, the arguments below do not establish convergence for every higher-degree input. Thus the overall resolution is partial.
Throughout, an input is fixed while $n$ tends to infinity through all its admissible population sizes.
Independently declare each directed contact from a type-$t$ vertex to a type-$u$ vertex live with probability $w_{tu}$. The final Independent Cascade infected set is precisely the set reachable from the seeds through live directed edges.
Indeed, one may sample every transmission trial before running the cascade. A successful transmission follows a live edge, so every infected vertex is reachable. Conversely, induction along a live directed path from a seed shows that every reachable vertex eventually becomes infected.
Write $R(v)$ for the set reachable from a vertex $v$, including $v$ itself.
Let
$$
\mathcal E=\{(u,t):d_{ut}>0\}.
$$
Reciprocity and positive masses imply that $d_{ut}>0$ exactly when $d_{tu}>0$, so $|\mathcal E|=m$.
A state $(u,t)$ means that a path has arrived at a type-$t$ vertex from a type-$u$ vertex. Define the nonnegative matrix $K$, indexed by $\mathcal E$, by
$$
K_{(u,t),(a,v)}
=
\begin{cases}
\bigl(d_{tv}-\mathbf 1_{\{v=u\}}\bigr)w_{tv},&a=t,\\
0,&a\neq t.
\end{cases}
$$
The subtraction removes the contact just traversed.
For each root type $t$, define the row vector $b_t$ by
$$
(b_t)_{(a,v)}
=
\begin{cases}
d_{tv}w_{tv},&a=t,\\
0,&a\neq t.
\end{cases}
$$
Denote the spectral radius of $K$ by $r(K)$.
Proposition. If $r(K)<1$, then
$$
C_t=1+b_t(I-K)^{-1}\mathbf 1
$$
is finite and, for every sufficiently large admissible $n$,
$$
\mathbb E[\rho_n]
\leq
\frac1n\sum_{t\in T}\mu_t\lambda_t C_t.
$$
Consequently,
$$
\rho_n\xrightarrow{\mathrm P}0,
\qquad
\nu=\delta_0.
$$
Proof. Fix any permitted simple contact graph and a type-$t$ root $v$.
Every vertex reachable from $v$ admits a simple live directed path from $v$. For a fixed simple path, its live probability is the product of its transmission probabilities, because its directed edges are distinct.
The sum of these products over simple paths of length $\ell$ is at most the corresponding sum over all nonbacktracking walks. The latter sum equals
$$
b_tK^{\ell-1}\mathbf 1,\qquad \ell\geq 1.
$$
To verify this identity, the first step has $d_{tv}$ possible contacts of each type $v$. After arrival in state $(u,t)$, there are exactly $d_{tv}-\mathbf 1_{\{v=u\}}$ allowed next contacts of type $v$. These counts hold for every permitted simple graph.
We use walk weights only as a deterministic upper bound. We do not interpret products along walks with repeated edges as probabilities.
Since $r(K)<1$, the finite-dimensional Neumann series converges and gives
$$
\mathbb E[|R(v)|]
\leq
1+\sum_{\ell\geq1}b_tK^{\ell-1}\mathbf 1
=
C_t.
$$
The infected set is contained in the union of the reachable sets of individual seeds. Seeds are independent of the live edges. Therefore its expected size is at most
$$
\sum_t n\mu_t\frac{\lambda_t}{n}C_t
=
\sum_t\mu_t\lambda_t C_t.
$$
This bound holds for every permitted graph, hence also after averaging over the conditioned graph construction. Division by $n$ and Markov’s inequality prove the result. $\square$
This strengthens the row-sum sufficient condition in the notes. If
$$
c=\max_t\sum_u d_{tu}w_{tu}<1,
$$
then every row sum of $K$ is at most $c$, so $r(K)\leq c<1$.
The strict spectral condition can be checked using rational arithmetic. For a nonnegative matrix $K$,
$$
r(K)<1
$$
is equivalent to the following condition: $I-K$ is invertible and
$$
v=(I-K)^{-1}\mathbf 1
$$
is strictly positive coordinatewise.
The forward implication follows from the Neumann series. Conversely, if $v>0$, then
$$
Kv=v-\mathbf 1.
$$
Nonnegativity of $K$ implies $v_i\geq1$. Conjugating $K$ by the diagonal matrix with diagonal $v$ gives row sums
$$
\frac{(Kv)_i}{v_i}=1-\frac1{v_i}<1.
$$
Thus its spectral radius, and hence that of $K$, is strictly less than one.
After reading the input, the nonzero pattern of $K$ can be constructed in
$$
O\bigl(m\min\{D,\tau\}+\tau\bigr)
$$
operations: every state has at most $\min\{D,\tau\}$ possible successors.
For a conservative bit bound, let
$$
H=L+\log(D+1)+\log(m+1).
$$
Clear denominators using the product of the input transmission denominators, whose bit length is at most $L$. Fraction-free elimination uses $O(m^3)$ integer operations on integers of $O(mH)$ bits, by the determinant bound for minors. Schoolbook arithmetic therefore gives a bound
$$
O\bigl((m+1)^5H^2+\tau L^2\bigr)
$$
for recognition and calculation of the displayed expectation constant.
On this recognized subclass, every allowed CDF cut answers YES, because
$$
\delta_0([0,x])=1
$$
for every $x\in[0,1]$.
We first prove the probability calculation used in the degree-two classification.
For $\theta>0$, write
$$
(\theta)_M=\theta(\theta+1)\cdots(\theta+M-1),
\qquad
(\theta)_0=1.
$$
Consider an exchangeable partition of $M$ labelled units whose probability for a specified partition $\pi$ is
$$
\Pr(\pi)
=
\frac{\theta^{|\pi|}\prod_{B\in\pi}(|B|-1)!}{(\theta)_M}.
$$
We need two instances.
Uniform permutation, $\theta=1$. A specified set of $s$ labels has $(s-1)!$ cyclic permutations. Counting permutations with a specified collection of cycle blocks gives the displayed formula, since $(1)_M=M!$.
Uniform two-stub pairing, $\theta=\tfrac12$. Give every unit two labelled stubs and pair all $2M$ stubs uniformly. A specified set of $s$ units forms one connected component in
$$
2^{s-1}(s-1)!
$$
pairings.
For $s\geq3$, there are $(s-1)!/2$ undirected cyclic orders and $2^s$ stub assignments. For $s=1$, there is one loop pairing; for $s=2$, there are two double-edge pairings. Thus the same formula holds for every $s\geq1$.
Since
$$
(2M-1)!!=2^M(1/2)_M,
$$
the probability of a specified component partition is exactly the displayed formula with $\theta=\tfrac12$.
Fix $k\geq1$ distinct marked units. Let $A_M$ be the number of units in blocks containing at least one mark.
Lemma. In either partition model,
$$
\frac{A_M}{M}
\Longrightarrow
\operatorname{Beta}(k,\theta).
$$
Here $\operatorname{Beta}(k,\theta)$ denotes the distribution on $(0,1)$ with density proportional to
$$
z^{k-1}(1-z)^{\theta-1}.
$$
Proof. Exchangeability allows us to label the marked units first.
The partition formula gives a sequential construction: after $j$ units have been assigned, the next unit joins an existing block of size $s$ with probability
$$
\frac{s}{j+\theta},
$$
and starts a new block with probability
$$
\frac{\theta}{j+\theta}.
$$
These probabilities follow by taking the ratios of the partition weights after enlarging a block or adding a singleton.
Let $A_j$ count units in marked blocks at this stage. Initially $A_k=k$, and
$$
\Pr(A_{j+1}=A_j+1\mid\text{current partition})
=
\frac{A_j}{j+\theta}.
$$
For a specified sequence with $r$ increments and $s$ nonincrements, multiplication of these transition probabilities gives
$$
\frac{(k)_r(\theta)_s}{(k+\theta)_{r+s}}.
$$
This is also the integral of $z^r(1-z)^s$ against the $\operatorname{Beta}(k,\theta)$ density. Consequently, the increment sequence has the same law as independent Bernoulli trials conditional on
$$
V\sim\operatorname{Beta}(k,\theta).
$$
In particular, conditionally on $V$,
$$
A_M=k+\operatorname{Binomial}(M-k,V).
$$
Its conditional variance divided by $M^2$ is at most $1/(4M)$, and its conditional mean divided by $M$ differs from $V$ by at most $k/M$. Hence $A_M/M$ converges to $V$ in mean square in this representation. $\square$
For the pairing model, we also need conditioning that forbids blocks of sizes one, or sizes one and two.
Let
$$
F\in\bigl\{\varnothing,\{1\},\{1,2\}\bigr\},
$$
and let $S_M$ be the event that no block has size in $F$.
Lemma. For $\theta=\tfrac12$,
$$
\Pr(S_M)\longrightarrow
\exp\left(-\theta\sum_{j\in F}\frac1j\right)>0.
$$
For each fixed $k\geq1$, conditioning on $S_M$ preserves the limit
$$
\frac{A_M}{M}\Longrightarrow\operatorname{Beta}(k,\theta).
$$
Proof. The partition weights give the generating-function identity
$$
\Pr(S_M)
=
\frac{[z^M](1-z)^{-1/2}g(z)}
{[z^M](1-z)^{-1/2}},
\qquad
g(z)=\exp\left(-\frac12\sum_{j\in F}\frac{z^j}{j}\right).
$$
Indeed, a block of size $j$ contributes exponential-generating-function weight $\theta z^j/j$. Summing over allowed blocks gives the numerator; summing over all blocks gives the denominator.
Put
$$
c_M=[z^M](1-z)^{-1/2}
=\frac{\binom{2M}{M}}{4^M}.
$$
Stirling’s formula gives
$$
c_M\sim(\pi M)^{-1/2}.
$$
It also supplies positive constants bounding $c_M$ above and below by constant multiples of $(M+1)^{-1/2}$. Therefore, for $0\leq j\leq M$,
$$
\frac{c_{M-j}}{c_M}
\leq C\sqrt{j+1},
$$
because
$$
\frac{M+1}{M-j+1}\leq j+1.
$$
For fixed $j$, this ratio tends to one.
Write $g(z)=\sum_jg_jz^j$. The function $g$ is entire, so Cauchy’s coefficient bound on any circle of radius greater than one gives geometric decay of $|g_j|$. Dominated convergence in the coefficient convolution now yields
$$
\Pr(S_M)
=
\sum_{j=0}^M g_j\frac{c_{M-j}}{c_M}
\longrightarrow
g(1).
$$
Next condition on the full blocks containing the marked units. The remaining
$$
R_M=M-A_M
$$
units have the same parameter-$\theta$ partition law: factoring the partition weight leaves precisely the product of block weights on the remaining labels, with its own normalization.
The beta limit from the preceding lemma has no atom at one, so $R_M$ tends to infinity in probability. Also, each fixed marked unit has a block-size fraction converging to $\operatorname{Beta}(1,\theta)$, which has no atom at zero. Thus the probability that any marked block has size in $F$ tends to zero.
The conditional probability of $S_M$, given the marked blocks, is
$$
\mathbf 1_{\{\text{marked blocks have no forbidden size}\}}
\Pr(S_{R_M}).
$$
It consequently tends in probability, and in mean, to $g(1)$.
For any bounded continuous function $f$, it follows that
$$
\mathbb E\left[f(A_M/M)\mathbf 1_{S_M}\right]
-
g(1)\mathbb E[f(A_M/M)]
\longrightarrow0.
$$
Division by $\Pr(S_M)\to g(1)>0$ proves preservation of the beta limit. $\square$
The two nontrivial simplicity probabilities are therefore
$$
e^{-1/2}
\quad\text{for }F=\{1\},
\qquad
e^{-3/4}
\quad\text{for }F=\{1,2\}.
$$
Suppose every unit is independently marked with probability $p_M$, where
$$
Mp_M\longrightarrow\Lambda.
$$
Marking is independent of the partition, including any of the preceding small-block restrictions.
Conditional on the number of marks $K_M=k$, the marked units are a uniform $k$-subset. Moreover,
$$
K_M\Longrightarrow\operatorname{Poisson}(\Lambda).
$$
Applying the preceding lemmas for each fixed $k$ gives the covered-fraction limit
$$
X_{\theta,\Lambda}\sim
e^{-\Lambda}\delta_0+
e^{-\Lambda}\sum_{k=1}^{\infty}
\frac{\Lambda^k}{k!}\operatorname{Beta}(k,\theta).
$$
To justify the infinite mixture, observe that $\mathbb E[K_M]=Mp_M$ stays bounded. Markov’s inequality gives a uniform tail bound for $K_M$. For any bounded continuous test function, truncate the sum over $k$, pass to the limit in its finitely many terms, and then let the truncation level increase.
Form an auxiliary undirected graph on the types, joining distinct types $t,u$ when $d_{tu}>0$. Within-type contacts are recorded separately by $d_{tt}$.
For a connected component $C$ of this auxiliary graph, define
$$
\alpha_C=\sum_{t\in C}\mu_t,
\qquad
\Lambda_C=\sum_{t\in C}\mu_t\lambda_t.
$$
Call $C$ productive in precisely the following cases.
Theorem. Every admissible input with $D\leq2$ has the weak limiting law
$$
\rho_n\Longrightarrow
Y=
\sum_{C\text{ productive}}\alpha_C X_{\theta_C,\Lambda_C},
$$
where the variables in the sum are independent. An empty sum means $Y=0$.
We prove both the classification and the asserted laws.
Every type has at most two distinct off-type neighbors. Hence every auxiliary component is a singleton, a path, or a cycle.
A cycle component must have at least three types. Each type already uses its two contacts on its two off-type neighbors, so all those counts are one and there are no within-type contacts. Reciprocity makes all masses in the ring equal.
For a path with at least two types, each interior type has one contact to each neighboring type and no within-type contact. An endpoint with total degree two has exactly one of these two forms:
An endpoint with total degree one has one contact to its neighboring type.
Finally, a singleton has $d_{tt}\in\{0,1,2\}$.
These possibilities exhaust all inputs with $D\leq2$.
For a degree-two type, after entering along one contact there is exactly one contact remaining. Thus the directed-state transition underlying $K$ is deterministic wherever the current type has degree two, and terminates wherever the current type has degree one.
For a ring, the states split into two directed cycles, one for each orientation. Their transmission products are
$$
a_+=\prod_{j=1}^r w_{t_jt_{j+1}},
\qquad
a_-=\prod_{j=1}^r w_{t_{j+1}t_j},
$$
with cyclic indexing.
A weighted directed-cycle matrix of length $p$ and weight product $a$ satisfies
$$
K^p=aI,
$$
and has spectral radius $a^{1/p}$. This follows directly by following the unique successor $p$ times; equivalently, its characteristic polynomial is $z^p-a$. Therefore a nonproductive ring has spectral radius strictly less than one in both orientation blocks.
For a path whose endpoints both have degree two, a nonbacktracking type walk traverses the path, turns at its ends, and returns. An endpoint with a within-type contact introduces one additional step before the turn. The states form one directed cycle, containing every supported ordered type pair exactly once. Its length is
$$
2(r-1)+e,
$$
where $e$ is the number of endpoints having a within-type contact. Its transmission product is less than one exactly when some supported directed probability is less than one. Hence a nonproductive such path again has spectral radius strictly less than one.
If a path has a degree-one endpoint, every directed-state walk terminates. It cannot turn at an interior type, and after any turn at the other endpoint it must reach a degree-one endpoint. Thus the directed-state graph is acyclic and its matrix is nilpotent.
For a singleton, the matrix is empty or zero when $d_{tt}\leq1$, and is the one-entry matrix $(w_{tt})$ when $d_{tt}=2$.
Applying Proposition 1 to each nonproductive component shows that its expected infected count stays bounded independently of $n$. Its contribution to $\rho_n$ therefore tends to zero in probability.
Let a ring have types $t_1,\ldots,t_r$. Their equal populations are
$$
N=n\mu_{t_j}.
$$
Each adjacent type pair is joined by a uniform bijection between its two vertex sets. The bijections are independent. Composing them around the ring gives a uniform permutation of the $N$ vertices of type $t_1$: condition on all but one of the bijections, and the remaining uniform bijection makes the composition uniform.
A permutation cycle of length $s$ corresponds to a contact component containing exactly $s$ vertices of every ring type. All contact graphs in this construction are simple, since every adjacent type pool has one stub per vertex.
Because one complete cyclic direction transmits deterministically, every seeded contact component is fully infected.
For a component corresponding to $s$ permutation units, the probability of having no seed is
$$
h_n^s,
\qquad
h_n=\prod_{t\in C}\left(1-\frac{\lambda_t}{n}\right).
$$
Seed statuses of different components are independent. Conditional on the component partition, this is exactly the same law as independently marking each permutation unit with probability $1-h_n$ and filling every marked block.
Furthermore,
$$
N(1-h_n)
\longrightarrow
\mu_{t_1}\sum_{t\in C}\lambda_t
=
\Lambda_C.
$$
The partition lemma with $\theta=1$ proves that the infected fraction within the ring converges to $X_{1,\Lambda_C}$. Its contribution to the whole society is therefore
$$
\alpha_CX_{1,\Lambda_C}.
$$
There is a particularly simple CDF in this case. Since $\operatorname{Beta}(k,1)$ has CDF $z^k$,
$$
\Pr(X_{1,\Lambda}\leq z)
=
e^{-\Lambda}\sum_{k=0}^{\infty}\frac{(\Lambda z)^k}{k!}
=
e^{-\Lambda(1-z)},
\qquad 0\leq z\leq1.
$$
Consider a path of $r\geq2$ types, all of total degree two.
Let $H_n$ be the number of stubs in any cross-type pool along the path. Reciprocity and the one-stub counts at interior types make this number the same along the entire path.
An endpoint with two off-type stubs has population $H_n/2$. An endpoint with one off-type stub and one within-type stub has population $H_n$; admissibility makes this population even. Thus $H_n$ is even. Put
$$
M_n=H_n/2.
$$
The cross-type matchings identify $H_n$ threads running from one endpoint to the other through the interior types. At either endpoint, these threads are joined in pairs:
Transport both endpoint pairings to one common set of $H_n$ thread labels. Conditional on the first endpoint pairing, the second is a uniform perfect matching. To verify this, condition on the endpoint pairings in their own labels and on all but one cross-type bijection. The remaining uniform bijection transports the second fixed pairing to a uniform perfect matching relative to the first.
Contract the pairs of the first endpoint pairing into $M_n$ labelled units. The second pairing is then precisely a uniform pairing of the two stubs at every unit. Hence the component partition has parameter $\theta=\tfrac12$.
A block of $s$ units contains $b_ts$ vertices of type $t$, where
$$
b_t=
\begin{cases}
1,&t\text{ is an endpoint with two off-type stubs},\\
2,&t\text{ is an interior type or an endpoint with a within-type stub}.
\end{cases}
$$
Indeed, the block uses $2s$ threads. Each interior type contributes one vertex per thread; a two-stub endpoint joins two threads at one vertex; a within-type endpoint contributes one vertex per thread. Thus, for every type in the component,
$$
n\mu_t=b_tM_n.
$$
The simplicity restrictions are also explicit.
Consequently, the only required conditioning is either $F=\varnothing$ or $F=\{1\}$, covered by Section 2.3.
All supported transmissions equal one, so a contact component is fully infected exactly when it contains a seed. For a block of $s$ units its no-seed probability is
$$
h_n^s,
\qquad
h_n=\prod_{t\in C}\left(1-\frac{\lambda_t}{n}\right)^{b_t}.
$$
As before, this is equivalent to independent unit marks with probability $1-h_n$. Since
$$
M_n(1-h_n)
\longrightarrow
\frac{M_n}{n}\sum_{t\in C}b_t\lambda_t
=
\Lambda_C,
$$
the partition lemma proves a limiting infected fraction $X_{1/2,\Lambda_C}$ within this component.
For a singleton with $d_{tt}=2$, use its vertices themselves as the units. The unconditioned model is the two-stub pairing model.
Its graph is simple exactly when there are no components of sizes one or two: these are respectively loops and double edges. Thus the conditioning is $F=\{1,2\}$.
When $w_{tt}=1$, every seeded cycle is fully infected. Independent unit marking has probability $\lambda_t/n$, and
$$
n\mu_t\frac{\lambda_t}{n}=\Lambda_C.
$$
Sections 2.3 and 2.4 therefore give $X_{1/2,\Lambda_C}$.
This includes, as a special case, the one-type law
$$
e^{-\lambda}\delta_0+
e^{-\lambda}\sum_{k=1}^{\infty}
\frac{\lambda^k}{k!}\operatorname{Beta}\left(k,\frac12\right).
$$
Different auxiliary components use disjoint stub pools. Their unconditioned matchings are independent, and simplicity is the intersection of separate events for these components. Conditioning therefore preserves their independence. Seeds and transmissions are also independent across them.
There are finitely many components for a fixed input. Each unit population tends to infinity because all supported masses are positive. The productive component fractions converge jointly to the independent limits above, while the sum of nonproductive contributions tends to zero in probability. Taking their weighted sum proves the theorem.
The classification and compact limiting-law description require
$$
O(m+\tau)
$$
operations after reading the input. Calculating $\alpha_C$ and $\Lambda_C$ gives a conservative schoolbook bit bound
$$
O\bigl((m+\tau+1)L^2\bigr).
$$
This is a running time for producing the analytic law description. It is not an asserted running time for deciding every exact CDF cut of sums of these mixtures.
Take nonisolated types $1,\ldots,k$ with
$$
d_{ii}=3,\qquad d_{ij}=0\quad(i\neq j),\qquad w_{ii}=1.
$$
An additional isolated type with seed intensity zero is allowed.
For each admissible $n$, let $N_i=n\mu_i$. Each $N_i$ is even. Conditioning the within-type pairing on simplicity gives a uniform labelled simple cubic graph: every such graph has exactly $(3!)^{N_i}$ stub representations. The conditioned graphs for different types remain independent.
We use the standard fixed-degree connectivity theorem: for each fixed integer $d\geq3$, a uniform labelled simple $d$-regular graph is connected with probability tending to one as its order tends to infinity through orders with even total degree. The stronger statement of asymptotic $d$-connectivity is given in [Wormald’s survey, Section 2.6](https://web.williams.edu/Mathematics/sjmiller/public_html/ntprob12/handouts/graphs/Womald_ModelsRandomGraphs.pdf).
Its hypotheses hold here: the degree is fixed at three, $N_i\to\infty$ because $\mu_i>0$, and $3N_i$ is even by admissibility.
Let $B_{i,n}$ indicate that type $i$ contains a seed. These indicators are independent and
$$
\Pr(B_{i,n}=0)
=
\left(1-\frac{\lambda_i}{n}\right)^{n\mu_i}
\longrightarrow
e^{-\mu_i\lambda_i}.
$$
With probability tending to one, all $k$ type graphs are connected. On that event,
$$
\rho_n=\sum_{i=1}^k\mu_iB_{i,n}.
$$
Thus the limiting law exists and equals the law of
$$
Y=\sum_{i=1}^k\mu_iB_i,
$$
where the $B_i$ are independent and
$$
\Pr(B_i=1)=1-e^{-\mu_i\lambda_i}.
$$
The finite indicator vector converges on a fixed finite state space, and the probability of graph disconnection tends to zero. This also proves total-variation convergence to this finite-support law.
Start with positive binary-encoded integers $a_1,\ldots,a_k$, and put
$$
S=\sum_{i=1}^k a_i.
$$
The question is whether some subset sums to $S/2$. Let $B$ denote the source input bit length.
Choose a power of two $M>S$. Define
$$
\mu_i=\frac{a_i}{M}\quad(1\leq i\leq k),
\qquad
\mu_0=1-\frac{S}{M}.
$$
Use the cubic construction on types $1,\ldots,k$ and make type zero isolated with $\lambda_0=0$.
All masses are positive dyadic rationals and sum to one. Reciprocity holds, and
$$
D=3,\qquad m=k,\qquad\tau=k+1.
$$
The existence promise is satisfied. For every sufficiently large admissible $n$, every nonisolated type population is even and at least four. A simple cubic graph exists at every such order: take an even cycle and add the matching joining opposite vertices.
Set
$$
J=2k+6,\qquad
\eta=2^{-J}.
$$
Use
$$
\log2
=
2\sum_{j=0}^{\infty}\frac1{(2j+1)3^{2j+1}}.
$$
This identity follows by integrating the geometric expansion of $2/(1-z^2)$ from zero to $1/3$.
Let $s_J$ be the sum of the first $J$ terms. Its positive remainder satisfies
$$
0<\log2-s_J
\leq
2\sum_{j=J}^{\infty}3^{-(2j+1)}
=
\frac34\,3^{-2J}
<
\frac{\eta}{8}.
$$
The last inequality holds since $J\geq8$.
Therefore
$$
r=s_J+\frac{\eta}{4}
$$
satisfies
$$
\log2+\frac{\eta}{8}<r<\log2+\frac{\eta}{4}.
$$
Put $P=2k+8$, so $2^{-P}=\eta/4$, and define
$$
\lambda_i
=
2^{-P}\left\lceil\frac{2^Pr}{\mu_i}\right\rceil.
$$
These intensities are dyadic. Upward rounding gives
$$
r\leq\mu_i\lambda_i
<
r+\mu_i2^{-P}
\leq r+\frac{\eta}{4}.
$$
Hence
$$
0<h_i:=\mu_i\lambda_i-\log2<\frac{\eta}{2}.
$$
For the limiting seed indicators, write
$$
p_i=1-e^{-\mu_i\lambda_i}.
$$
Then
$$
0<p_i-\frac12
=
\frac12(1-e^{-h_i})
<
\frac{h_i}{2}
<
\eta.
$$
Thus the indicators are strictly, but very slightly, biased above one half.
Large intensities cause no validity problem: for each fixed constructed input, $\lambda_i/n\leq1$ for every sufficiently large $n$, as required by the task.
Ask
$$
x=\frac{S}{2M},\qquad q=\frac12.
$$
Both are valid dyadic cuts. The limiting-law query becomes
$$
F_p:=
\Pr\left(\sum_{i=1}^ka_iB_i\leq\frac S2\right)
\geq\frac12.
$$
For comparison, let $C_i$ be independent fair Bernoulli variables and put
$$
Z=\sum_i a_iC_i.
$$
Complementing every coordinate sends $Z$ to $S-Z$, so
$$
\Pr(Z\leq S/2)
=
\frac12+\frac12\Pr(Z=S/2).
$$
This identity also holds when $S$ is odd.
Couple the indicators with independent uniform variables $U_i$:
$$
C_i=\mathbf 1_{\{U_i\leq1/2\}},
\qquad
B_i=\mathbf 1_{\{U_i\leq p_i\}}.
$$
Then $B_i\geq C_i$ and
$$
\Pr\bigl((B_i)_i\neq(C_i)_i\bigr)
\leq
\sum_i(p_i-\tfrac12)
<
k\eta.
$$
If a partition exists, at least one fair indicator vector has sum $S/2$, giving
$$
\Pr(Z\leq S/2)\geq\frac12+2^{-(k+1)}.
$$
Therefore
$$
F_p
\geq
\frac12+2^{-(k+1)}-k\eta
>
\frac12,
$$
because $k\leq2^k$ implies
$$
k\eta\leq2^{-(k+6)}.
$$
If no partition exists, the fair lower-tail probability is exactly one half. Coordinatewise domination makes the biased lower-tail event a subset of the fair lower-tail event.
The containment has strictly positive probability difference. On the event
$$
\frac12<U_i\leq p_i\qquad\text{for every }i,
$$
which has probability $\prod_i(p_i-\tfrac12)>0$, all fair indicators are zero and all biased indicators are one. Since $S>0$, the fair lower-tail event occurs and the biased one does not. Consequently,
$$
F_p<\frac12.
$$
We have proved
$$
\text{the partition instance is YES}
\quad\Longleftrightarrow\quad
\nu([0,x])\geq\frac12.
$$
Both directions have strict separation from the cut. No undecided equality case is used.
The exponent defining $M$ is $O(B)$. Every output mass and intensity has $O(B+k)$ bits. For the intensities, this follows from
$$
\left\lceil\frac{2^Pr}{\mu_i}\right\rceil
\leq 2^PM+1,
$$
since $r<1$ and $\mu_i\geq1/M$.
Including dense zero tables and the query, the output length is
$$
L=O\bigl(k(B+k)\bigr).
$$
The series calculation uses $O(k)$ rational terms. Taking products of their denominators gives intermediate integers of $O(k^2)$ bits. Subsequent rounding calculations use integers of $O(B+k^2)$ bits. With schoolbook arithmetic, a conservative total reduction time is
$$
O((B+k)^5).
$$
This is a polynomial many-one reduction with
$$
m=k,\qquad\tau=k+1,\qquad D=3.
$$
Therefore any algorithm correctly deciding these exact limiting-law cuts is $\mathrm{NP}$-hard. In particular, a running time polynomial in $m,\tau,L,D$ for all admissible inputs with limiting laws would imply
$$
\mathrm P=\mathrm{NP}.
$$
The hardness result applies to an admissible subclass whose weak limits were proved explicitly. It therefore remains valid independently of the universal existence question.
The new degree-two theorem resolves all maximum-degree-two inputs, including their multitype deterministic critical structures. The spectral criterion also gives a graph-uniform convergence-to-zero result at arbitrary degree.
What is still missing is a proof or counterexample for universal weak convergence when higher-degree types occur. The arguments here do not control general reducible directed transmission, including deterministic critical structures connected to higher-degree types.
The [finite-tree cascade algorithm](https://ojs.aaai.org/index.php/AAAI/article/download/16844/16651) concerns a fixed finite tree; the cubic graphs used in the reduction lie outside that setting. The [configuration-model epidemic CLTs](https://arxiv.org/abs/1812.03105) include fixed initial infective counts conditional on a large outbreak, but do not establish the missing universal convergence statement or decide these exact CDF cuts.
⟨structured verdict parsed — rendered above⟩
Overall assessment: partial, with substantial valid results. The output proves the stated spectral convergence criterion, the degree-two limiting-law classification, and $\mathrm{NP}$-hardness of exact CDF cuts on an admissible degree-three subclass with proved limiting laws. It does not settle weak convergence for every admissible input, as it explicitly acknowledges.
I found no false central step in the arguments supplied. The blocking issue is the missing universal convergence result.
The representation is correct. Sampling independent directed transmission trials beforehand produces exactly the vertices reachable from seeds through live directed edges. The two inclusions follow from the cascade’s infection rule and induction along a live path.
Directed trials on opposite orientations of a contact remain distinct, as required by the task.
Positive masses and reciprocity imply
$$
d_{ut}>0\quad\Longleftrightarrow\quad d_{tu}>0,
$$
so the state set has cardinality $m$.
The transition count
$$
d_{tv}-\mathbf 1_{\{v=u\}}
$$
correctly removes the contact just traversed. It is nonnegative on every indexed transition.
For any permitted simple graph, the weighted number of nonbacktracking walks of length $\ell$ from a type-$t$ root is
$$
b_tK^{\ell-1}\mathbf 1.
$$
The identity uses the prescribed contact counts at each vertex, so it does not require any averaging over graph construction.
Every reachable vertex has a simple live path from the root. Such a path uses distinct directed edges, making its live probability the stated product. Enlarging the sum to all nonbacktracking walks is a valid deterministic upper bound. The output correctly avoids treating repeated-edge walk weights as probabilities.
Under $r(K)<1$, the Neumann series converges and yields the displayed finite bound $C_t$.
The union bound over seeded roots, together with independence of seeds and live edges, gives
$$
\mathbb E[\rho_n]
\leq
\frac1n\sum_t\mu_t\lambda_tC_t.
$$
This holds for each permitted graph and therefore survives conditioning on simplicity. Markov’s inequality proves convergence in probability to zero.
Zero transmission probabilities, zero seed intensities, and isolated types cause no substantive difficulty.
The equivalence used for recognition is correct. If
$$
v=(I-K)^{-1}\mathbf 1>0,
$$
then nonnegativity gives $v_i\geq1$, and diagonal conjugation produces row sums
$$
1-\frac1{v_i}<1.
$$
There are finitely many rows, so their maximum is strictly below one.
The matrix construction bound accounts for at most $\min\{D,\tau\}$ successors per state. Clearing transmission denominators gives the stated coefficient-size bound; determinant bounds and fraction-free elimination support the conservative bit complexity
$$
O\bigl((m+1)^5H^2+\tau L^2\bigr).
$$
The CDF conclusion is correct: for every allowed $x$, $\delta_0([0,x])=1$, so every allowed cut answers YES.
Assessment: proved.
The permutation count $(s-1)!$ is correct.
For the two-stub pairing model, the count
$$
2^{s-1}(s-1)!
$$
is correct for $s\geq3$ and agrees with the separately checked loop and double-edge cases. The normalization
$$
(2M-1)!!=2^M(1/2)_M
$$
therefore gives the claimed partition law.
Exchangeability permits placing the marked labels first. At that stage all $k$ initial units belong to marked blocks, regardless of their initial partition.
The sequential probabilities derived from the partition weights are correct. Consequently, covered and uncovered units evolve with initial weights $k$ and $\theta$. The displayed sequence probability
$$
\frac{(k)_r(\theta)_s}{(k+\theta)_{r+s}}
$$
matches the beta integral.
The conditional binomial representation and its variance and mean bounds establish the claimed weak limit.
The generating function correctly deletes block weights $\theta z^j/j$ for forbidden sizes.
The coefficient estimate is valid. In particular,
$$
\frac{M+1}{M-j+1}\leq j+1
$$
throughout the asserted range. Together with geometric decay of the entire function’s coefficients, this justifies dominated convergence.
Conditioning on the complete marked blocks leaves the same partition model on the remaining labels. The beta limits imply both that the remaining population tends to infinity in probability and that marked blocks have forbidden size with probability tending to zero.
The conditional probability of the restriction therefore converges to its positive limiting constant. The bounded-test-function argument validly proves preservation of the beta limit.
The constants $e^{-1/2}$ and $e^{-3/4}$ are correct.
Independent marking gives a binomial mark count with the stated Poisson limit. Conditional on its count, the marked set is uniform. The uniform tail bound justifies passing from fixed-count limits to the infinite mixture, including the zero-mark atom.
Assessment: proved.
The auxiliary graph has maximum degree two, so its components are singletons, paths, or cycles.
The listed endpoint patterns exhaust the integer contact counts compatible with total degree at most two. Reciprocity forces equal populations around a ring and the asserted population ratios along paths.
For degree-two vertices, removing the arrival contact leaves exactly one possible continuation. The resulting state descriptions are correct:
For each weighted state cycle, the identity $K^p=aI$ and spectral radius $a^{1/p}$ are correct. A nonproductive cyclic component has product strictly below one because all factors belong to $[0,1]$.
Applying the spectral criterion therefore gives a bounded expected infected count in every nonproductive component.
Independent cross-type bijections compose to a uniform permutation. Its cycles correspond to contact components with equal numbers of vertices of each ring type.
These graphs are automatically simple. A deterministic cyclic transmission direction reaches the entire contact component from any seed.
The no-seed probability $h_n^s$ correctly implements independent unit marking, and
$$
N(1-h_n)\longrightarrow\Lambda_C.
$$
The resulting mixture law and its displayed CDF are correct, including the atom at zero.
The common thread count, its evenness, and the contracted unit count $M_n=H_n/2$ follow from the endpoint populations and admissibility.
Transporting the endpoint pairings through a uniform cross-type bijection gives the stated uniform two-stub pairing model. The vertex multiplicities $b_t$ correctly account for every endpoint pattern.
The simplicity restrictions are exhaustive:
The seed calculation gives
$$
M_n(1-h_n)\longrightarrow\Lambda_C,
$$
so the partition lemmas apply with the required conditioning.
For a single degree-two type, forbidden block sizes one and two are exactly loops and double edges. The marking intensity is correct.
Separate auxiliary components use independent randomness, and conditioning on their separate simplicity events preserves independence. The finite-component joint convergence and vanishing nonproductive contributions justify the weighted-sum law.
The stated time bounds concern classification and production of an analytic description. The output explicitly—and correctly—does not claim that these bounds decide exact CDF cuts.
Assessment: proved.
Conditioning a cubic pairing on simplicity produces a uniform labelled simple cubic graph because each such graph has $(3!)^{N_i}$ stub representations.
The connectivity theorem is stated with the needed hypotheses. Section 2.6 of [Wormald’s survey](https://web.williams.edu/Mathematics/sjmiller/public_html/ntprob12/handouts/graphs/Womald_ModelsRandomGraphs.pdf) confirms asymptotic connectivity for uniform simple regular graphs of fixed degree at least three. Here the degree is three, each positive-mass population tends to infinity, and admissibility supplies the parity restriction.
The seed indicators are independent and have the stated limiting probabilities. On simultaneous connectivity, deterministic transmission infects exactly those complete type populations containing seeds. The resulting finite-support weak limit, and the stronger total-variation conclusion, follow.
Choosing a power of two $M>S$ gives positive dyadic masses summing to one, including the isolated type.
Reciprocity holds, and $D=3$, $m=k$, and $\tau=k+1$ are correct. The even-cycle construction with opposite-vertex matching provides a simple cubic graph at every even order at least four, so the existence promise is satisfied.
The series identity and tail calculation are correct:
$$
2\sum_{j=J}^{\infty}3^{-(2j+1)}
=
\frac34\,3^{-2J}.
$$
The subsequent bounds on $r$, upward dyadic rounding, and $h_i$ follow with the stated constants.
In particular,
$$
0<p_i-\frac12<\eta
$$
holds for every constructed indicator. Large fixed intensities are permitted because the seeding rule applies only for sufficiently large populations.
Both query values are valid dyadic rationals.
Complement symmetry gives the correct fair lower-tail identity, including odd $S$. The coupling bounds the change in any event probability by less than $k\eta$.
For YES instances, the equality mass supplies the claimed margin, and
$$
k\eta\leq2^{-(k+6)}
$$
is sufficient to preserve strict separation above one half.
For NO instances, coordinatewise domination gives containment of the biased lower-tail event in the fair one. The displayed positive-probability coupling event proves strict containment in probability, hence strict separation below one half.
Thus the many-one reduction has the correct direction and does not depend on resolving equality at the threshold.
The output-size bounds are polynomial. Dense zero tables fit the displayed bound since $k\leq B$. Intermediate rational calculations have the stated conservative bit sizes, and the reduction-time bound is polynomial.
Assessment: the $\mathrm{NP}$-hardness claim is proved on the stated subclass. It remains valid independently of universal convergence.
Major issue — universal convergence is not established. The task asks whether a weak limiting law exists for every admissible input. The spectral criterion, degree-two classification, and cubic reduction subclass do not cover all higher-degree inputs.
This is an openly acknowledged limitation, not an internal contradiction. It nevertheless prevents completion of the assigned task.
Minimum actionable feedback: retain the proved results and explicitly resolve the remaining universal existence question. Another special-case convergence result or an analytic law description alone would not discharge that quantifier. No expositional correction to the supplied arguments fills this gap.
The required overall status is therefore partial. Under the prescribed schema, continuous_status must be unresolved, although the degree-three hardness result itself stands.
⟨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.