We are very grateful to Michael Krivlevich who provided numerous valuable comments and links to relevant work. Josh Erde offered useful feedback. Finally we would like to thank the anonymous referees for useful comments and suggestions. Any typos or inaccuracies are the sole responsibility of the authors of this paper.


NP hardness proofs
Here we present the proofs that stopping contagion and minimizing contagion are NP-hard. We assume throughout this section that every vertex has threshold \(r=2\) .
Stopping contagion
We first introduce a slight variant of stopping contagion and prove it is NP-Hard.
Definition 9 In the stopping contagion by vertex deletion problem, we are given as input a graph \(G=(V,E)\) , two disjoints sets of vertices \(A, B \subseteq V\)  and a parameter \(\ell \) . Given that all vertices in \(A\)  are active, our goal is to determine whether it is possible to ensure no (remaining) vertices from \(B\)  are infected by deleting at most \(\ell \)  vertices from \(G\) . Deleting vertices from \(A\)  and \(B\)  is allowed.

Theorem 23 
The stopping contagion by vertex deletion problem is NP-Complete.

Clearly, this problem is in NP; we show that is it NP-Hard by reducing it to vertex cover. Recall, for a graph \(G = (V, E)\)  and a parameter \(\ell \) , an instance of Vertex Cover asks whether there exists a subset \(R \subseteq V\)  of size at most \(\ell \)  such that every edge in \(E\)  intersects \(R\) . Given such an instance of Vertex Cover, we construct the following bipartite graph \(G^{\prime } = (A, B, F)\) :
\(A &= V \\B &= \lbrace w_{st}: (s,t) \in E)\rbrace  \\F &= \lbrace  (v, w_{st}) \in V \times E : v = s\ \text{or}\ v = t \rbrace \) 
In words, we let \(A\)  and \(B\)  represent the vertices and edges of \(G\)  respectively, connecting each edge in \(B\)  to both its corresponding endpoints in \(A\) . Clearly \(G^{\prime }\)  can be obtained from \(G\)  in polynomial time. We now prove there is a vertex cover of size at most \(\ell \)  in \(G = (V, E)\)  if and only if it is possible to delete \(\ell \)  or fewer vertices in \(G^{\prime } = (A, B, F)\)  to stop contagion.
If there is a vertex cover \(R\)  of size at most \(\ell \)  in \(G\)  then deleting \(R\)  from \(G^{\prime }\)  will ensure that no vertex in \(B\)  is activated, as every node in \(B\)  has at least one neighbor in \(R\)  and exactly two neighbors in \(A\) . On the other hand, suppose we can delete a set of size at most \(\ell \)  from \(G^{\prime }\)  ensuring that no vertex in \(B\)  is activated after deletions. Notice that without loss of generality, we may assume only vertices in \(A\)  are deleted. This is because if some node \(w_{st} \in B\)  is deleted, we could instead delete \(s \in A\)  while preserving the safety of all vertices in \(B\) , since \(w_{st}\)  has exactly two neighbors. Now let \(R\)  be a set of at most \(\ell \)  nodes whose deletion from \(A\)  results with every vertex in \(B\)  inactive. The point is that \(R\)  must be a vertex cover in \(G\) ; otherwise, there would an edge \((s,t)\)  in \(G\)  not covered by \(R\) , which would imply \(w_{st} \in B\)  will be infected even after \(S\)  is deleted as both \(s\)  and \(t\)  are seeds. This contradiction concludes the proof.
Sometimes, deleting a vertex from \(A\)  or \(B\)  might be impossible (e.g., shutting down a transportation hub that is too central). The problem above remains hard even if we are not allowed to delete vertices from \(A \cup B\) , although we leave the proof for the supplementary.
Theorem 24 The stopping contagion by vertex deletion problem is NP-Complete, even when the additional constraint is added that only vertices in \(V \setminus (A \cup B)\)  may be deleted.

The proof of Theorem REF  illustrates that the vertex deletion problem remains NP-Hard even if no deletions of nodes from \(B\)  are allowed. To show hardness in the case where \(A \cup B\)  are disallowed, start with \(G^{\prime }\)  constructed in the proof. We further modify \(G^{\prime }\)  to include \(A^{\prime }=\lbrace s,t\rbrace \)  connected to all vertices in \(A\) . The proof follows by taking the set of seeds to equal \(A^{\prime }\) , since these vertices immediately activate all vertices in \(A\) .
We can now leverage these results to show hardness results for the edge deletion problem we were interested in.
Theorem 25 
The stopping contagion decision problem is NP-Complete.

Consider an input to the vertex deletion problem. \(G=(V,E)\)  with disjoint \(A, B \subseteq V\)  as the set of active protected and nodes respectively. By the proof of Theorem  REF , we may assume \(V=A \cup B\)  and insist only deletions from \(A\)  are allowed. We transform \(G\)  to an input graph \(G^{\prime }=(V^{\prime },E^{\prime })\)  for the edge deletion problem as follows.
We take \(V^{\prime }\)  to be the vertex set of \(G\) , together with a set \(Z\)  disjoint from \(V\)  of cardinality \(2|A|\) . The vertices in \(V\)  are connected in \(G^{\prime }\)  as they are in \(G\) . The vertices in \(Z\)  are divided to \(|A|\)  disjoint pairs: \(\lbrace z_{2i-1}, z_{2i}\rbrace \)  for \(1 \le i \le |A|\) . Suppose that \(A=\lbrace a_i : 1 \le i \le |A|\rbrace .\)  Every vertex \(a_i \in A\)  is connected (only) to \(z_{2i}\)  and \(z_{2i-1}\)  in \(Z\) . No edge in \(G^{\prime }\)  connects a vertex in \(Z\)  to a vertex in \(V \setminus A\) . Finally, we let the set of active and protected vertices in \(G^{\prime }\)  be \(A^{\prime } = Z\)  and \(B^{\prime } = B\)  respectively. \(G^{\prime }\)  can clearly be constructed from \(G\)  in polynomial time.
We claim that we can stop every vertex in \(B\)  from being infected (in \(G\) ) from the set of seeds \(A\)  by deleting at most \(\ell \)  vertices from \(A\)  if and only if we can stop the vertices \(B\)  from getting infected (in \(G^{\prime }\) ) from the seed set \(A\)  by deleting at most \(\ell \)  edges. Indeed, if we can stop contagion in \(G\)  by deleting \(R\subseteq A\)  with \(|R| \le \ell \) , we can stop contagion in \(G^{\prime }\)  by deleting at most \(\ell \)  edges by simply deleting a single edge from every pair in \(Z\)  connected to a vertex in \(R\) . On the other hand, if we can stop contagion in \(G^{\prime }\)  by deleting at most \(\ell \)  edges, we can stop contagion in \(G\)  by deleting at most \(\ell \)  vertices in \(A\) . This is because we can simply delete every vertex in \(A\)  that is incident (in \(G^{\prime }\) ) to an edge deleted from \(G^{\prime }\) . (Observe that every edge in \(G^{\prime }\)  is adjacent to a vertex in \(A\) .)
We conclude this subsection by showing that stopping contagion remains hard even if \(|A|=2\)  and \(|B|=1\) .
Theorem 26 The stopping contagion decision problem is NP-Complete when \(|A| = 2\)  and \(|B| = 1\) .

We will show the \(|A| = 2\)  and \(|B| = 1\)  cases are hard separately over the following two lemmas. Taken together, the reductions in Lemma REF  and Lemma REF  naturally compose, which proves our desired result.
<FIGURE>Lemma 10 
The stopping contagion decision problem is NP-Complete when \(|A| = 2\) .

Given an instance of the stopping contagion problem on a graph \(G = (V, E)\)  with \(A, B \subseteq V\) , we construct a new instance on a graph \(G^{\prime } = (V^{\prime }, E^{\prime })\)  with \(A^{\prime } = \lbrace s, s^{\prime }\rbrace \)  with the same optimum. We do this by attaching a large set of vertices \(Z = \lbrace  z_i : 1 \le i \le |E| + 1 \rbrace \)  to the graph \(G\) , and connecting these with \(A\)  and \(A^{\prime }\) . More precisely, we build \(G^{\prime } = (V^{\prime }, E^{\prime })\)  by adding the vertices in \(Z\)  in the following way.
\(V^{\prime } &= V \cup Z \cup A^{\prime } \\E^{\prime } &= E \cup (A^{\prime } \times Z) \cup (Z \times A)\) 
Suppose the stopping contagion problem had an optimum of \(\ell \)  in the original graph; we now argue that \(G^{\prime }\)  has the same. First, notice that the optimum is at most \(\ell \) : deleting the edges which correspond to the original optimal solution will effectively stop the contagion. In the new graph, \(A^{\prime }\)  will infect the vertices in \(C\)  and \(A\) , but the deleted edges will then prevent the contagion from spreading to \(B\) .
Now assume, for sake of contradiction, there exists a way to delete \(\ell ^{\prime } < \ell \)  edges in \(G^{\prime }\)  to stop contagion. Given only \(\ell ^{\prime }\)  edges are deleted, it is impossible to prevent the vertices in \(A\)  from being infected. This is because each vertex in \(A\)  is connected to all \(|E| + 1\)  vertices in \(C\) , which in turn get infected by \(A^{\prime }\) —to prevent this from happening would require deleting at least \(|E| \ge \ell > \ell ^{\prime }\)  edges. Since \(G\)  is embedded in \(G^{\prime }\) , this would imply that deleting fewer than \(\ell \)  edges is possible to prevent contagion from spreading from vertices in \(A\)  to \(B\) , contradicting the optimality of \(\ell \)  in the original instance.
This shows that solving the stopping contagion problem in \(G^{\prime }\)  can be used to solve the stopping contagion problem in \(G\) , completing the reduction. Since reduction in the opposite direction is trivial, this shows that the two problems are equivalent under polynomial time reduction.
Lemma 11 
The stopping contagion decision problem is NP-Complete when \(|B| = 1\) .

We reduce the general problem of stopping contagion to the case where \(|B|=1\) . In similar fashion to the previous proof, given an instance of the stopping contagion problem on a graph \(G = (V, E)\)  with \(A, B \subseteq V\) , we construct the following graph \(G^{\prime } = (V^{\prime }, E^{\prime })\)  with \(B^{\prime } = \lbrace t\rbrace \) .
\(V^{\prime } &= V \cup S \cup Z \cup B^{\prime } \\E^{\prime } &= E \cup ((B \cup S) \times Z) \cup (Z \times B^{\prime })\) 

Here, \(S = \lbrace s\rbrace \)  and \(Z\)  is an additional large set of \(|E| + 1\)  vertices introduced to the graph. We now prove that if original instance has optimum \(k\) , then the stopping contagion problem on \(G^{\prime } = (V^{\prime }, E^{\prime })\)  with \(A^{\prime } = A \cup S\)  and \(B^{\prime }\)  also has optimum exactly \(\ell \) .
It is not hard to see that deleting \(k\)  edges is sufficient to prevent contagion of \(B^{\prime }\)  in \(G^{\prime } = (V^{\prime }, E^{\prime })\) . This follows from the observation that it is possible to remove \(\ell \)  edges to prevent vertices in \(A^{\prime }\)  from contaminating those in \(B\) : \(S\)  by itself does not affect the percolation process in the embedded original graph. If \(B\)  remains inactive, despite the presence of \(S\) , so will the vertices in \(Z\)  and thus \(B^{\prime } = \lbrace t\rbrace \) .
To complete the reduction, assume, for sake of contradiction, it was possible to delete \(\ell ^{\prime } < \ell \)  edges in \(G^{\prime }\)  to stop contagion. If a single vertex in \(B\)  gets infected, so will every vertex in \(Z\) , thus infecting \(B^{\prime }\)  Ṗreventing this would require deleting at least \(|E| \ge \ell > \ell ^{\prime }\)  edges; hence, such a solution could not allow any vertex in \(B\)  from being infected. Once again, exploiting the fact that \(S\)  does not affect the percolation process in the embedded graph \(G\) , this would imply there exists a way to delete at most \(\ell ^{\prime }\)  edges in \(G\)  to stop contagion. However, this is a contradiction since \(\ell \)  is supposed to be the optimum in the original problem, proving our desired result.

Minimizing contagion
Theorem 27 The minimizing contagion decision problem is NP-Complete.

The decision problem is clearly in NP, so we prove it is NP-Hard by reduction from stopping contagion. Recall the in the stopping contagion problem we are given a graph \(G = (V, E)\)  on \(n\)  vertices, two disjoint subsets \(A, B \subseteq V\)  and a parameter \(\ell \) . The goal is to determine whether \(B\)  can be protected from infection by deleting at most \(\ell \)  edges. From Lemma REF , we can further assume \(B = \lbrace b\rbrace \) . Given such an instance, we transform it into an input of the minimizing contagion problem as follows.
We create a graph \(G^{\prime }\)  from \(G\)  by adding a set \(Z\)  of \(2n\)  vertices. We then choose an arbitrary vertex \(a \in A\)  and connect all vertices in \(Z\)  to both \(a\)  and \(b\) . Finally, we set the maximum number of infections allowed as \(n - 1\)  and ask if this possible with \(\ell \)  edge deletions. Observe that we can assume \(\ell \le n-1\)  since we can always prevent \(b\)  from infection by deleting edges to all other vertices in \(G\) .
If we can protect \(B\)  from activation by \(A\)  in \(G\) , then deleting the same set of edges from \(G^{\prime }\)  ensures that \(B\)  is not infected from \(A\)  in \(G^{\prime }\) . As a result, no vertex in \(Z\)  will be infected in \(G^{\prime }\)  either, since each has exactly two neighbors: \(a\)  and \(b\) . Since \(G\)  has \(n\)  vertices, this means that at most \(n-1\)  vertices can be infected in \(G^{\prime }\) . Therefore, if the first problem is solvable with at most \(\ell \)  edge deletions, so is the minimizing contagion problem on the constructed instance.
To complete the proof, assume we can delete at most \(\ell \)  edges in \(G^{\prime }\)  to prevent more than \(n-1\)  vertices from being infected. Since \(\ell \le n-1\) , at least \(n\)  vertices in \(Z\)  must be connected to both \(a\)  and \(b\)  even after edges are deleted. It follows that \(b\)  cannot be infected, lest these \(n\)  vertices in \(Z\)  become infected as well. Since \(G\)  is embedded in \(G^{\prime }\) , we have shown that it is possible to prevent \(b\)  from infection in \(G\)  by deleting at most \(\ell \)  edges from \(G\) .
Putting these results together, it follows that we can prevent the activation of \(b\)  in \(G\)  by deleting at most \(\ell \)  edges from \(G\)  if and only if we can ensure at most \(n-1\)  vertices in \(G^{\prime }\)  are activated by deleting at most \(\ell \)  edges from \(G^{\prime }\) . This concludes the proof.

Algorithms for graphs of bounded treewidth
We begin by defining the following problem, which is similar to the Influence Diffusion Minimization problem considered by Cordasco, Gargano & Rescigno [1]}.
Definition 10 (Generalized Influence Diffusion Minimization) 
Consider a graph \(G = (V, E)\)  with corresponding threshold function \(t: V \rightarrow \mathbb {N}\)  and subsets \(A, B \subseteq V\) . Given a budget \(\ell \) , the generalized influence diffusion problem asks to minimize the number of vertices in \(B\)  infected through setting up to \(\ell \)  thresholds to \(+\infty \)  for vertices in \(A\) .

This problem uses a more flexible infection model than we initially considered: a vertex \(v \in V\)  becomes infected after at least \(t(v)\)  of its neighbors are infected, a threshold which is allowed to differ across vertices. For simplicity, we refer to this infection model as \(t\) -neighbor bootstrap percolation. Here, the initial set of infected vertices (seeds) are those having threshold 0. Vertices whose thresholds are set to \(+\infty \)  are called immunized; these vertices can never be infected.
We now show the generalized influence diffusion problem can be solved efficiently on graphs with bounded treewidth, providing a dynamic programming algorithm. To simply our algorithm, we first introduce a more convenient notion of tree decomposition and note it can also be computed quickly.
Definition 11 (Nice Tree Decomposition) 
A rooted tree decomposition \((T, X)\)  of a graph \(G = (V, E)\)  is called nice if it satisfies the following additional properties.


If \(X_r\)  represents the root of \(T\) , \(X_r\)  and all leaves are empty.

Every non-leaf node falls into one of the three categories below.

Introduce Node: A node \(X_i\)  with exactly one child \(X_j\)  such that \(X_i = X_j \cup \lbrace  u \rbrace \)  for some \(u \notin X_j\) .

Forget Node: A node \(X_i\)  with exactly one child \(X_j\)  such that \(X_i = X_j - \lbrace  u \rbrace \)  for some \(u \in X_j\) .

Join Node: A node \(X_i\)  with exactly two children \(X_j\)  and \(X_k\)  with \(X_i = X_j = X_k\) .


We need algorithms that compute tree decompositions. It suffices for our purpose to find, given a graph of treewidth \(w\)  a tree decomposition of width \(O(k)\) .
Proposition 2 
Given a graph \(G = (V, E)\)  on \(n\)  vertices with treewidth \(\tau \) , a tree decomposition with width at most \(4\tau +3\)  can be found in \(O(27^{\tau } n^2)\) . Let \((T, X)\)  be one such tree decomposition with \(n^{\prime }\)  nodes; from this, a nice tree decomposition can be computed in time \(O(\tau \max \lbrace  n, n^{\prime }\rbrace )\)  with width at most \(4 \tau + 3\)  and number of nodes bounded by \(O(\tau n)\) .

The first part of the proposition regarding finding a decomposition of width at most \(4\tau +3\)  is due to [2]}. The second part regarding nice tree decompositions is from [3]}. We are now ready to state our main result.
Proposition 3 
Consider an instance of the generalized influence diffusion problem on a graph \(G = (V, E)\)  with \(A, B \subseteq V\) , threshold function \(t\)  and budget \(\ell \) . If \(G = (V, E)\)  has treewidth \(\tau \) , this problem is solvable in time
\(O(n^2 27^\tau + \tau n \cdot \ell 81^\tau \min \lbrace r, \Delta \rbrace ^{4\tau } \cdot (16^\tau + \ell )) \\\) 
Here, \(n\)  is the number of vertices in \(G\)  and \(\Delta \)  its maximum degree. \(r\)  is the maximum assumed by the threshold function \(t\) .

From Proposition REF , a nice tree decomposition of \(G = (V, E)\)  can be computed efficiently once we obtained our tree decomposition. For this tree decomposition \((T, X)\)  with root \(X_r\) , we introduce the shorthand below to simplify notation.
[noitemsep]
\(T(i)\)  denotes the subtree rooted at \(X_i\) .

\(X(i)\)  represents the union of all bags in \(T(i)\) , including \(X_i\)  itself.

\(G(i)\)  denotes the subgraph of \(G\)  induced by vertices in \(X(i)\) .

\(n_i\)  is the cardinality of bag \(X_i\) .

We now present a dynamic programming algorithm which recursively computes subproblem values at each bag under different hypotheses. To that end, fix a bag \(X_i\)  and notice after infection spreads each vertex is
either infected; inactive but not immunized (safe); or immunized and therefore inactive. We denote these states with the letters n, s and m respectively. Let \(S_i\)  represent the set of all legal mappings \(s\)  from the vertices in \(X_i\)  to states. A legal mapping is defined as one where no vertices outside \(A\)  are mapped to the immunized state; these are basically the mappings which are “possible.”
\(s: X_i \rightarrow \lbrace  \texttt {n}, \texttt {s}, \texttt {m}\rbrace \) 
Similarly, let \(T^{\prime }_i\)  represent the set of all mappings \(t^{\prime }\)  from vertices in \(X_i\)  to possible threshold values. These mappings will help account for the effect of infected vertices in \(V - X(i)\)  on the vertices on \(X_i\)  in \(T(i)\) : note all edges between \(V - X(i)\)  and \(X(i)\)  must involve vertices in \(X_i\)  in any tree decomposition. As such, for each vertex \(u \in X_i\)  we only care about thresholds of 0 up to \(t(u)\) .
\(t^{\prime }: X_i \rightarrow \mathbb {N},\ t^{\prime }(u) \in \lbrace 0, \dots , t(u)\rbrace \) 
Now, denote as \(B_i(p, s, t^{\prime })\)  the minimum number of \(B\) -vertices that can be infected in \(G(i)\)  by immunizing at most \(p\)  \(A\) -vertices in \(X(i)\) , where the states and thresholds of vertices in \(X_i\)  are given by \(s\)  and \(t^{\prime }\)  respectively. These are precisely the subproblem values which are computed in a bottom-up fashion at each bag \(X_i\) , for all \(s \in S_i\)  and \(t^{\prime } \in T^{\prime }_i\)  and \(0 \le p \le \ell \) . For bags with no vertices, and hence no legal state or threshold mappings, we aim to compute \(B_i(p, \phi , \phi )\)  for all \(0 \le p \le \ell \) , where \(\phi \)  denotes an empty mapping. (If a bag has no vertices, there is only a single subproblem value to compute for each \(p\) .)
By construction, \(B_r(\ell , \phi , \phi )\)  is our desired valued, since \(X_r = \phi \) . For every leaf \(X_i\) , it is immediately clear \(B_i(p, \phi , \phi ) = 0\)  for all
\(0 \le p \le \ell \) . With this in place, all that remains to specify the algorithm and prove its correctness is to show how a bag's subproblem values can be correctly computed from those of its children—we give the update rules below, building off those given by

Introduce Nodes. Let \(X_i = X_j \cup \lbrace  u \rbrace \)  be an introduce node with child \(X_j\) . For a state mapping \(s\)  on \(X_i\) , let \(\tilde{s}\)  be the corresponding restriction to \(X_j\)  so \(\tilde{s}(v) = s(v)\)  for all \(v \in X_j\) ; define \(\tilde{t}^{\prime }\)  with respect to \(t^{\prime }\)  analogously. For some threshold mapping \(\tilde{t}^{\prime }\)  on \(X_j\)  and set \(S \subseteq X_j\) , we also define
\((\tilde{t}^{\prime } - S)(v) ={\left\lbrace \begin{array}{ll}\tilde{t}^{\prime }(v) - 1 &: v \in S \\\tilde{t}^{\prime }(v) &: v \notin S.\end{array}\right.}\) 
In words, \(\tilde{t}^{\prime } - S\)  starts with \(\tilde{t}^{\prime }\)  and decrements all thresholds of vertices in \(S\)  by 1. Finally, we denote with \(N_i(s)\)  the set of infected neighbors of \(u\)  among vertices in \(X_i\)  according to some state mapping \(s\) . Using this new notation, we write the update rule as follows:
\(B_i(p, s, t^{\prime }) ={\left\lbrace \begin{array}{ll}1\lbrace  v \in B\rbrace  + \min \limits _{\begin{array}{c}N \subseteq N_i(s) \\ |N|=t^{\prime }(u)\end{array}} B_j(p, \tilde{s}, \tilde{t}^{\prime } - (N_i(s) - N)) &: \begin{array}{c}s(u) = \texttt {n} \\ t^{\prime }(u) \le |N_i(s)|\end{array} \\B_j(p, \tilde{s}, \tilde{t}^{\prime }) &: \begin{array}{c}s(u) = \texttt {s} \\ t^{\prime }(u) > |N_i(s)|\end{array} \\B_j(p - 1, \tilde{s}, \tilde{t}^{\prime }) &: s(u) = \texttt {m} \\+\infty &: \text{otherwise.} \\\end{array}\right.}\) 

Forget Nodes. Let \(X_i = X_j - \lbrace  u \rbrace \)  be a forget node with child \(X_j\) . Here, for state mappings \(t^{\prime }\)  and \(s\)  on \(X_i\) , denote
\(\tilde{t}^{\prime }(v) = {\left\lbrace \begin{array}{ll}\max \lbrace 0, t(v) - N_i(s)\rbrace  &: v = u \\t^{\prime }(v) &: v \ne u,\end{array}\right.}\) 
where \(N_i(s)\)  is defined as above. To compute our desired subproblem problem values, we take the minimum over all, at most three, states \(u\)  could be in.
\(B_j(p, s, t^{\prime }) = \min _{\begin{array}{c}\tilde{s} \in S_j \\ \tilde{s}(v) = s(v) \\ \forall v \in X_i\end{array}} B_j(p, \tilde{s}, \tilde{t}^{\prime })\) 

Join Nodes. Let \(X_i\)  be a join node with children \(X_j\)  and \(X_k\)  satisfying \(X_i = X_j = X_k\) . For a state mapping \(s\)  on \(X_i\) , let \(M(s)\)  denote the total number of immunized vertices among those in \(X_i\) . We can express our update equations as follows:
\(B_i(p, s, t^{\prime }) = \min _{\begin{array}{c}p_j + p_k = p + M(s) \\ p_j, p_k \ge M(s)\end{array}} \left\lbrace  B_j(p_j, s, t^{\prime }) + B_k(p_k, s, t^{\prime }) \right\rbrace .\) 

The correctness of these rules immediately follow from the definition of \(B_i(p, s, t^{\prime })\)  given above; this can be formalized through induction. We therefore conclude the proof by providing an analysis of this algorithm's running-time.
First, note the nice tree decomposition provided by Proposition REF  has at most \(O(\tau n)\)  nodes, where \(n\)  is the number of vertices in \(V\) . The total subproblem values that must be computed at each bag \(X_i\)  is either \(\ell \)  or the product of \(\ell \)  and the cardinalities of \(S_i\)  and \(T_i\) . Notice each vertex has at most 3 legal states, so we can immediately bound the number of mappings in \(S_i\)  as
\(|S_i| \le 3^{n_i} \le 3^{(4\tau + 3) + 1}.\) 
In the last step, we use the tree decomposition's width to constrain the size of the bag. To bound the size of \(T_i\) , consider that under any mapping in \(T_i\) , \(t^{\prime }(u) \in \lbrace 0, \dots , t(u)\rbrace \) , where \(u\)  is some vertex in \(X_i\) . If \(r\)  represents the largest threshold under the threshold function given, the image of \(t^{\prime }(u)\)  can take on at most \(r + 1\)  values. Furthermore, since \(u\)  can have at most \(\deg (u)\)  infected neighbors, we technically need only consider \(\deg (u) + 1\)  values of \(t^{\prime }(u)\)  from \(t(u)\)  to \(t(u) - \deg (u)\) . We can bound this using \(\Delta \) , the maximum degree of the graph. Combining these observations yields the bound below.
\(|T_i| \le \min \lbrace r + 1, \Delta + 1\rbrace ^{n_i} \le \min \lbrace r + 1, \Delta + 1\rbrace ^{(4\tau + 3) + 1}\) 
Computing the update for introduce nodes requires taking a minimum across subsets \(N \subseteq N_i(s)\) ; since \(N_i(s)\)  has at most \(n_i \le (4\tau +3) + 1\)  elements, this involves at most \(2^{(4\tau +3) + 1}\)  terms. Forget and join nodes similarly are similarly expressed as minimums over \(O(1)\)  and \(O(\ell )\)  terms respectively. Multiplying the total number of bags, subproblems per bag and work required per subproblem yields the claimed runtime, after accounting for the time to compute the nice tree decomposition as well.
\(O(n^2 27^\tau + \tau n \cdot \ell 81^\tau \min \lbrace r, \Delta \rbrace ^{4\tau } \cdot (16^\tau + \ell ))\) 
This result allows us to derive efficient algorithms for minimizing contagion and stopping contagion on bounded treewidth instances.
Proposition 4 
Consider the minimizing contagion problem on a graph \(G = (V, E)\)  with \(A \subseteq V\)  and parameter \(k\)  under the \(r\) -neighbor bootstrap percolation infection model. The minimum of the edge deletions required to ensure at most \(k\)  additional infections occurs can be computed in time
\(O\left((n + m)^2 27^\tau + m \cdot \tau (n + m) \cdot m 81^\tau \min \lbrace r, \max \lbrace \Delta , 2\rbrace  \rbrace ^{4\tau } \cdot (16^\tau + m) \right).\) 
Here, \(n\)  and \(m\)  are the number of vertices and edges in \(G\)  respectively while \(\Delta \)  is the maximum degree of \(G\) .

From \(G = (V, E)\)  we construct a new graph \(G^{\prime } = (V^{\prime }, E^{\prime })\)  by subdividing each edge \(e \in E\) . Namely, every edge \(e=(u,v) \in E\)  is replaced with the two edges \((u,w_{u,v})\)  and \((w_{u,v},v)\) . We can write \(V^{\prime } = V \cup W\) , where \(W\)  represents the set of new vertices in \(G^{\prime }\)  which correspond to edges in \(G\) . Construct the threshold function
\(t(u) ={\left\lbrace \begin{array}{ll}r &: u \in V - A \\0 &: u \in A \\1 &: u \in W,\end{array}\right.}\) 
and set \(A^{\prime } = W\) , \(B^{\prime } = V - A\) . There is a clear correspondence between how infection spreads in \(G\)  and \(G^{\prime }\)  under the \(r\) -neighbor and \(t\) -neighbor bootstrap percolation models respectively. Notice that immunizing a threshold 1 vertex \(u \in A^{\prime }\)  adjacent to \(v\)  and \(w\)  corresponds to deleting the edge \((v, w)\)  in \(G\) , since infection cannot spread from one neighbor to the other.
Consider solving the generalized influence diffusion problem on the graph \(G^{\prime } = (V^{\prime }, E^{\prime })\)  with \(A^{\prime }\) , \(B^{\prime }\)  and \(t\)  as defined above for budget \(\ell \) . From the relationship highlighted above, this gives the minimum additional infections possible in \(G\)  using at most \(\ell \)  edge deletions. To solve the minimizing contagion problem, we can simply try all possible values of \(\ell \)  and return the smallest value which keeps the number of additional infections below \(k\) .
Now let the number of vertices and edges in \(G\)  be \(n\)  and \(m\)  respectively. To compute the runtime of this algorithm, we determine the time complexity of solving the generalized influence diffusion problem on \(G^{\prime }\)  and multiply this by \(m\) , the number of values of \(\ell \)  iterated over. To that end, we attempt to relate properties of \(G^{\prime }\)  to those of the input \(G\) . First, notice subdividing edges of a graph preserves treewidth and
\(|V^{\prime }| = n + m,\ |E^{\prime }| = 2m.\) 
The maximum degree of the graph is also very nearly preserved, although some additional degree 2 vertices are now introduced. Finally, the maximum of the threshold function as defined is \(r\) , assuming \(r > 0\) . Plugging this into the runtime given in Proposition REF  and including the \(m\)  pre-factor gives us the desired runtime.
\(O\left((n + m)^2 27^\tau + m \cdot \tau (n + m) \cdot m 81^\tau \min \lbrace r, \max \lbrace \Delta , 2\rbrace  \rbrace ^{4\tau } \cdot (16^\tau + m) \right)\) 
Proposition 5 Consider the stopping contagion problem on a graph \(G = (V, E)\)  with disjoint \(A, B \subseteq V\)  under the \(r\) -neighbor bootstrap percolation infection model. Given all vertices in \(A\)  are infected, the minimum number of edge deletions necessary to ensure that no vertices from \(B\)  are infected can be computed in time
\(O\left((n + m)^2 27^\tau + m \cdot \tau (n + m) \cdot m 81^\tau \min \lbrace r, \max \lbrace \Delta , 2\rbrace  \rbrace ^{4\tau } \cdot (16^\tau + m) \right).\) 
Here, \(n\)  and \(m\)  are the number of vertices and edges in \(G\)  respectively while \(\Delta \)  is the maximum degree of \(G\) .

We take a nearly identical approach to that used in Proposition REF . Once again, we subdivide each edge to obtain \(G^{\prime } = (V^{\prime }, E^{\prime })\) , where \(V^{\prime } = V \cup W\) . Here, \(W\)  represents the set of new vertices in \(G^{\prime }\)  which correspond to edges in \(G\) . Now we define
\(t(u) ={\left\lbrace \begin{array}{ll}r &: u \in V - A \\0 &: u \in A \\1 &: u \in W,\end{array}\right.}\) 
and let \(A^{\prime } = W\) , \(B^{\prime } = B\) . With this threshold function, there is a correspondence between how infection spreads in \(G\)  and \(G^{\prime }\) ; this is discussed further in the proof of Proposition REF .
In light of this connection, consider the solution of the generalized influence diffusion problem on the graph \(G^{\prime } = (V^{\prime }, E^{\prime })\)  with \(A^{\prime }\) , \(B^{\prime }\)  and \(t\)  as defined above for budget \(\ell \) . This gives us the number of infected vertices in \(B\)  if \(\ell \)  or fewer edges in \(G\)  are deleted to minimize number of infections in \(B\) . Therefore, to solve the stopping contagion problem, we can simply try all possible values of \(\ell \)  and return the smallest value which allows 0 vertices in \(B\)  to be infected.
A similar analysis to the on in the proof of Proposition REF  yields an identical runtime, as desired.
\(O\left((n + m)^2 27^\tau + m \cdot \tau (n + m) \cdot m 81^\tau \min \lbrace r, \max \lbrace \Delta , 2\rbrace  \rbrace ^{4\tau } \cdot (16^\tau + m) \right)\) 
