# Local treewidth of random and noisy graphs with applications to stopping
contagion in networks

Hermish Mehta  Daniel Reichman

###### Abstract

We study the notion of local treewidth in sparse random graphs: the maximum
treewidth over all $k$-vertex subgraphs of an $n$-vertex graph. When $k$ is
not too large, we give nearly tight bounds for this local treewidth parameter;
we also derive tight bounds for the local treewidth of noisy trees, trees
where every non-edge is added independently with small probability. We apply
our upper bounds on the local treewidth to obtain fixed parameter tractable
algorithms (on random graphs and noisy trees) for edge-removal problems
centered around containing a contagious process evolving over a network. In
these problems, our main parameter of study is $k$, the number of initially
“infected” vertices in the network. For the random graph models we consider
and a certain range of parameters the running time of our algorithms on
$n$-vertex graphs is $2^{o(k)}\operatorname{poly}(n)$, improving upon the
$2^{\Omega(k)}\operatorname{poly}(n)$ performance of the best-known algorithms
designed for worst-case instances of these edge deletion problems.

##  1 Introduction

Treewidth is a graph-theoretic parameter that measures the resemblance of a
graph to a tree. We begin by recalling the definition of treewidth.

######  Definition 1 (Tree Decomposition).

A tree decomposition of a graph $G=(V,E)$ is a pair $(T,X)$, where $X$ is a
collection of subsets of $V$, called bags, and $T$ a tree on vertices $X$
satisfying the properties below:

  1. 1.

The union of all sets $X_{i}\in X$ is $V$.

  2. 2.

For all edges $(u,v)\in E$, there exists some bag $X_{i}$ which contains both
$u$ and $v$.

  3. 3.

If both $X_{i}$ and $X_{j}$ contain some vertex $u\in V$, then all bags
$X_{k}$ on the unique path between $X_{i}$ and $X_{j}$ in $T$ also contain
$u$.

######  Definition 2 (Treewidth).

The width of a tree decomposition $(T,X)$ is one less than cardinality of the
largest bag. More formally, we can express this as

$\displaystyle\max_{i}|X_{i}|-1.$

The treewidth of a graph $G=(V,E)$ is the minimum width among all tree
decompositions of $G$.

Many graph-theoretic problems that are NP-hard admit polynomial-time
algorithms on graph families whose treewidth is sufficiently slowly growing as
a function of the number of vertices [37]. There is vast literature concerned
with finding methods to relate the treewidth of graphs to other well-studied
combinatorial parameters and leveraging this to devise efficient algorithms
for algorithmic problems in graphs with constant or logarithmic treewidth
[19]. An excellent introduction to the concept of treewidth as well as brief
survey of the work of Robertson and Seymour in establishing this concept can
be found in Chapter 12 of [21].

These treewidth-based algorithmic methods, however, have historically found
limited applicability in random graphs. Sparse random graphs $G(n,d/n)$ where
every edge occurs independently with probability $d/n$, for some $d>1$,
exhibit striking contrast between their local and global properties—and this
contrast is apparent when looking at treewidth. Locally, these graphs appear
tree-like with high probability111Given a random graph model, we say an event
happens with high probability if it occurs with probability tending to $1$ as
$n$ tends to infinity. (w.h.p.): the ball of radius $O(\log_{d}n)$ around
every vertex looks like a tree plus a constant number of additional edges.
Globally, however, these graphs have w.h.p. treewidth $\Omega(n)$. For
example, the super-critical random graph $G(n,\frac{1+\delta}{n})$ has w.h.p.
treewidth $\Omega(n)$ [22, 50, 43]. As a result of this global property,
conventional techniques used to exploit low treewidth to derive efficient
algorithms do not apply directly for random graphs.

In this paper, we take advantage of the local tree-like structure of random
graphs by analyzing the _local_ behavior of treewidth in random graphs.
Central to our approach is the following definition.

######  Definition 3 (Local Treewidth).

Let $G$ be an undirected $n$-vertex graph. Given $k\leq n$ we denote by
$t_{k}(G)$ the largest treewidth of a subgraph of cardinality $k$ of $G$.

In words, the local treewidth of an $n$-vertex graph, with locality parameter
$k$, is the maximum possible treewidth across all subgraphs of size $k$. We
study two models of random graphs, starting with the familiar binomial random
graph $G(n,p)$. While the binomial random graph $G(n,p)$ lacks many of the
characteristics of empirically observed networks such as skewed degree
distributions, studying algorithmic problems on random graphs can nevertheless
lead to interesting algorithms.

######  Definition 4 (Noisy Trees).

Let $T$ be an $n$ vertex tree. The noisy tree $T^{\prime}$ obtained from $T$
is a random graph model where every non edge of $T$ is added to $T$
independently, with probability $1/n$.

Here we assume $p=1/n$ for convenience; all our results regarding noisy trees
also hold when the perturbation probability $p$ satisfies $p=\epsilon/n$ for
$\epsilon<1$. Noisy trees are related to small world models of random networks
[49, 48], where adding a few random edges to a graph of high diameter such as
a path results with a graph of logarithmic diameter w.h.p. [41].

Below, we give an informal description of the concepts we study and sketch our
main results; we defer discussion of formal results until Section 2 and later
in the paper. Our main result is a nearly tight bound holding w.h.p. for the
maximum treewidth of a $k$-vertex subgraph of $G(n,p)$ assuming $k\leq
n^{1-\epsilon}$ for $\epsilon\in(0,1)$ and $p=d/n$ where $d>1$. In the
notation introduced earlier, this provides a bound for $t_{k}(G)$. Assuming
$k\leq n^{\epsilon}$ for a sufficiently small $\epsilon$ we obtain nearly
tight bounds for the local treewidth of noisy trees as well.

Our upper bounds on the local treewidth are motivated by algorithmic problems
related to containing the spread of a contagious process over undirected
graphs by deleting edges. We focus on the bootstrap percolation contagious
process (Definition 5) where there is a set of initially infected vertices and
noninfected vertices are infected if they have at least $r\geq 2$ neighbors
and consider two edge-removal problems: _Stopping Contagion_ and _Minimizing
Contagion_. Informally, in stopping contagion we are given a subset of
infected nodes $A$ and seek to remove a minimal number of edges to ensure a
“protected” subset of vertices $B$ (disjoint from $A$) are not infected from
$A$. In minimizing contagion we wish to ensure at most $m$ additional vertices
are infected from $A$ for a target value $m$ by deleting a minimal number of
edges. Such edge removal problems might arise, among other applications [25,
26], in railways and air routes, where the goal might be to prevent spread
while also minimizing interference to transportation. In this context, edge
deletion may correspond to removing a transportation link altogether or
introducing special requirements (such as costly checks) to people between the
the endpoints. Edge removal can be also viewed as a _social distancing_
measure to control an epidemic outbreak [5]. One can also study the problem of
removing _vertices_ to control the spread of an epidemic which is related to
vaccinations: making nodes immune to infection and removing them from the
network [54].

We design algorithms for stopping and minimizing contagion for random graphs
and noisy trees. Note that our algorithms do not achieve polynomial time, even
for $k$ that is poly-logarithmic in $n$; whether there exists a polynomial
time algorithm for minimizing contagion and stopping contagion in $G(n,p)$ for
every value of $k$ is an open question. Nonetheless, the dependency of our
algorithm on $k$ is better (assuming $k\leq n^{\epsilon}$ for an appropriate
constant $\epsilon>0$) than the dependency of $k$ in the running time of the
best known algorithms for minimizing contagion222We are not aware of previous
algorithms for the stopping contagion problem. in the worst case [18]. Please
see Subsection 2.3 for details.

Our algorithms are based on the following three observations:

  1. 1.

The local treewidth of binomial random graphs and noisy trees is sublinear in
$k$.

  2. 2.

There exist fast algorithms for minimizing and stopping contagion in graphs of
bounded treewidth.

  3. 3.

The set of seeds $A$ has what we call the _bounded spread_ property: w.h.p. at
most $c|A|$ additional vertices are infected from $A$ for some constant333For
$G(n,d/n)$, our constant $c:=c(d)$ is a function of $d$. When $d$ is a
constant independent of $n$ so is $c$. $c$. Bounded spread allows us to solve
minimizing contagion and stopping contagion on subgraphs that have small
(sublinear in $k$) treewidth.

For the sake of brevity and readability we focus on _edge_ deletion problems.
We note that our algorithms can be easily adapted for the analogous problems
of minimizing and stopping contagion by deleting _vertices_ rather than edges.
The reason is that our algorithms for minimizing/stopping contagion on bounded
treewidth graphs work (with the same asymptotic running time guarantees) for
vertex deletion problems. Combining algorithms for bounded treewidth with the
bounded spread property as well the upper bound on the local treewidth yields
algorithms for the vertex deletion versions of minimizing and stopping
contagion.

Our main contribution is studying the concept of local treewdith for random
graphs and connecting it to algorithmic problems involving stopping contagion
in networks. Our calculations are standard and the contribution is conceptual
rather than introducing a new technique. Our results for noisy trees regarding
the bounded spread property are interesting as in contrast to other infection
models considered in the literature [10], the influence of adding random “long
range” edges to the total spread of a seed set with at most $n^{1-\epsilon}$
vertices is minor in the sense that w.h.p. the total spread increases as a
result only by a constant multiplicative factor.

##  2 Our results

###  2.1 Local treewidth bounds

Recall we define the local treewidth of a graph $G$, denoted $t_{k}(G)$, to be
the greatest treewidth among along subgraphs of size $k$. Trivially, for any
graph with at least one edge and $k\leq n$, $1\leq t_{k}(G)\leq k$.

Consider as an illustrative example the random graph $G=G(n,1/2)$: with high
probability, $t_{k}(G)=\Omega(k)$ for all values of $k$. For $k\leq 1.9\log n$
this follows as there is a clique of size $k$ in $G$ w.h.p. For $k>1.9\log n$
this follows as a randomly chosen subset of size $k$ has, with high
probability, minimum degree $\Omega(k)$, and a graph with treewidth $r$ has a
vertex of degree at most $r$.

We can now state our bounds for $t_{k}$ in the random graph models we
consider. From here onward, $\epsilon>0$ is taken to be a positive constant in
$(0,1)$. We give somewhat compressed statements; reference to the full
Theorems are provided throughout this section.

######  Theorem 1.

Let $G=G(n,p)$ with $p=d/n$ and $k\leq n^{1-\epsilon}$. Then, with high
probability:

$\displaystyle t_{k}(G)\leq 3+O\left(\frac{k\log d}{\log n}\right).$

Since it is always the case that $t_{k}(G)\leq k$, the upper bound in the
Theorem above becomes trivial if $d\geq n^{\Omega(1)}$. Also observe that the
Theorem does not hold for arbitrary $k\leq n$, as for $k=n,t_{k}(G)=\Omega(n)$
w.h.p. In terms of lower bounds, we have the following:

######  Theorem 2.

Suppose $p=d/n$ and $d>1+\delta$ where $\delta>0$ is a constant (not depending
on $n$). Suppose $k\leq O(n/\log n)$; then, w.h.p.

$\displaystyle t_{k}(G)\geq\Omega\left(\frac{k}{\log n}\right).$

More details can be found in Section 3. Our upper and lower bounds for the
local treewidth of $G(n,d/n)$ also extend to the random $d$-regular graph
$G(n,d)$–details can be found in Subsection 3.3.

For noisy trees, we have the following results.

######  Theorem 3.

Let $T$ be an $n$-vertex tree with maximum degree $\Delta$. Let $T^{\prime}$
be a noisy tree obtained from $T$. Then w.h.p.

$\displaystyle t_{k}(T^{\prime})\leq 3+O\left(\frac{k(\log k+\log\Delta)}{\log
n}\right).$

Observe that the upper bound in the Theorem is trivial if $k,\Delta$ are
$n^{\Omega(1)}$. As a result, in our proofs we will assume $k,\Delta\leq
n^{\epsilon},$ for sufficiently small $\epsilon>0$. Our results can be
extended to the case where each non-edge is added with probability $c/n$ for
$c>1$. Similar ideas (which are omitted) yield the upper bound:

$\displaystyle t_{k}(T^{\prime})\leq 3+O\left(\frac{k(\log k+\log\Delta+\log
c)}{\log n}\right).$

We also provide a lower bound, showing that up to the $\log k,\log\Delta$
terms, the upper bound above is tight. Namely, the noisy path has w.h.p. local
treewidth of order $\Omega(k/\log n)$. For more details on the lower and upper
bounds please see Section 4.

###  2.2 Contagious process and edge deletion problems

The local treewidth results outlined above prove useful in the context of two
edge deletion problems we study. These problems arise when considering the
evolution of a contagious processes over an undirected graph.

We focus on the $r$-neighbor bootstrap percolation model [15].

######  Definition 5.

In $r$-neighbor bootstrap percolation we are given an undirected graph
$G=(V,E)$ and an integer _threshold_ $r\geq 1$. Every vertex is either
_active_ (we also use the term infected) or _inactive_ ; a set of vertices
composed entirely of active vertices is called active. Initially, a set of
vertices called _seeds_ , $A_{0}$, is activated. A contagious process evolves
in discrete steps, where for integral $i>0$,

$\displaystyle A_{i}=A_{i-1}\cup\\{v\in V:|N(v)\cap A_{i-1}|\geq r\\}.$

Here, $N(v)$ is the set of neighbors of $v$. In words, a vertex becomes active
in a given step if it has at least $r$ active neighbors. An active vertex
remains active throught the process and cannot become inactive. Set

$\displaystyle\langle A_{0}\rangle=\bigcup_{i}A_{i}.$

The set $\langle A_{0}\rangle$ is the set of nodes that eventually get
infected from $A_{0}$ in $G$. Clearly, $\langle A_{0}\rangle$ depends on the
graph $G$, so we sometimes write $\langle A_{0}\rangle_{G}$ to call attention
to the underlying graph. We say a vertex $v\in V$ gets _activated_ or
_infected_ from a set of seeds $A_{0}$ if $v\in\langle A_{0}\rangle$.

It is straightforward to extend this definition to the case where every vertex
$v$ has its own threshold $t(v)$ and a vertex is infected only if it has at
least $t(v)$ active neighbors at some point. As is customary in bootstrap
percolation models, we usually assume that all thresholds are larger than $1$.
Now, given a network with an evolving contagious process, we introduce the
stopping contagion problem:

######  Definition 6 (Stopping Contagion).

In the stopping contagion problem, we are given as input a graph $G=(V,E)$
along with two disjoints sets of vertices, $A,B\subseteq V$. Given that the
seed set is $A$, the goal is to compute the minimum number of edge deletions
necessary to ensure that no vertices from $B$ are infected. In other words, we
want to make sure $\langle A\rangle_{G^{\prime}}\cap B=\phi$, where
$G^{\prime}$ is the graph obtained from $G$ after edge deletions. Given an
additional target parameter, $\ell$, the corresponding decision problem asks
whether it is possible to ensure no vertices from $B$ are infected by deleting
at most $\ell$ edges.

Next we consider the setting where given a set of infected nodes, we want to
remove the minimal number of edges to ensure no more than $s$ additional
vertices are infected.

######  Definition 7.

In the minimizing contagion problem, we are given a graph $G=(V,E)$, a subset
of vertices $A\subseteq V$ and a parameter $s$. Given that the seed set is
$A$, we want to compute the minimum number of edge deletions required to
ensure at most $s$ vertices in $V\setminus A$ are infected. If $G^{\prime}$ is
the graph obtained from $G$ by edge deletions, then this condition is
equivalent to requiring $|\langle A\rangle_{G^{\prime}}|\leq|A|+s$. In the
decision problem, we want to decide if it is possible to ensure $|\langle
A\rangle_{G^{\prime}}|\leq|A|+s$ with at most $\ell$ edge deletions.

Both stopping contagion and minimizing contagion are NP-complete, and stopping
contagion remains NP-hard even if $|A|=2$ and $|B|=1$. For complete proofs,
please refer to the Appendix.

###  2.3 Algorithmic results

For minimizing contagion, current algorithmic ideas [18] can be used to prove
that if $|A|$ and the optimal solution are of size $O(k)$ the problem can be
solved in time $2^{O(k)}\operatorname{poly}(n)$ on $n$-vertex graphs. No such
algorithm, parameterized by $|A|$ and the size of the optimal solution, is
known for stopping contagion. Using our upper bounds for local treewidth,
however, we can prove:

######  Theorem 4.

Let $\epsilon$ be a constant in $(0,1)$. Suppose that $k\leq n^{1-\epsilon}$
and that every vertex has threshold greater than $1$. Let $G:=G(n,p)$ where
$p=d/n$. Assuming $d$ is a constant, we have that w.h.p. both minimizing
contagion and stopping contagion can be solved in $G$ in time
$2^{o(k)}\operatorname{poly}(n)$.

######  Theorem 5.

Suppose that $k\leq n^{\epsilon}$ for sufficiently small $\epsilon\in(0,1)$
and that every vertex has a threshold greater than $1$. Let $T^{\prime}$ be a
noisy tree where the base tree $T$ has maximum degree $\Delta=O(1)$. Then
w.h.p. both minimizing contagion and stopping contagion can be solved in
$T^{\prime}$ in time $2^{o(k)}\operatorname{poly}(n)$.

We stress that the set $A$ of seeds can be chosen in arbitrary way. In
particular, an adversary can pick $A$ _after_ the random edges in our graph
models have been chosen.

The dependence of the running time on $n,k,d$ and $\Delta$ can be made
explicit: for precise statements, please see Section 6. Algorithms for grids
and planar graphs are presented in Section 6 as well.

For our purpose, to translate local treewidth bounds to algorithmic results,
we need an algorithm for solving stopping contagion and minimizing contagion
on graphs of low treewidth. We provide such an algorithm that runs in
exponential time in the treewidth, assuming the maximum degree is not too
large, using ideas from [18]. More details can be found in Section 5.

###  2.4 Our techniques

Our upper bounds for the local treewidth build on a simple “edge excess
principle”: A $k$-vertex connected graph with $k+r$ edges has treewidth at
most $r+1$. As the treewidth of a set of connected components is the maximum
treewidth of a component, it suffices to analyze the number of edges in
connected subgraphs of the random graphs we study. For $G(n,p)$ this is
straightforward, but for noisy trees it is somewhat more involved. We find it
easier to first analyze the edge excess of connected subgraphs, before
considering connecting edges that allow us bound the excess of arbitrary
subgraphs.

A key component in our lower bound is the simple fact that if $H$ is a minor
of $G$ then $\operatorname{tw}(G)\geq\operatorname{tw}(H)$. Therefore it
suffices to prove the existence of large treewidth subgraphs that are minors
w.h.p. of random graphs and noisy trees. Recall that an $n$-vertex graph is
called an $\alpha$-_expander_ if there exists $\alpha\in(0,1)$ such that every
subset $S$ of vertices with at most $n/2$ vertices has at least $\alpha|S|$
neighbors not in $S$. We use the fact [40] that for any graph $H$ with $k$
vertices and edges, assuming $k=O(n/\log n)$ an $n$-vertex expander $G$ has an
embedding444See Subsection 2.8 for further details on minor-theoretic concepts
we use. of $H$ as a minor in $G$. Furthermore, every connected subgraph of $G$
corresponding to a vertex in $H$ is of size $O(\log n)$. The lower bound then
follows as it is known that $G(n,\frac{1+\delta}{n})$ contains with high
probability [39, 40] a subgraph with $\Omega(n)$ vertices that is an
$\alpha$-expander for an appropriate choice $\alpha$. Similar ideas are used
to prove the existence of large minors with linear treewidth in the noisy
trees (e.g., the noisy path).

Our algorithms for minimizing contagion and stopping contagion in graphs of
bounded treewidth build on techniques designed to exploit the tree-like nature
of low treewidth graphs, sharing similarities to algorithms for target set
selection in [11], where target set selection is the problem of finding a
minimal set that infects an entire graph under the bootstrap percolation
model. More directly, our problem resembles the Influence Diffusion
Minimization (IDM) studied in [18], where the goal is to minimize the spread
of the $r$-neighbor bootstrap percolation process by preventing spread through
vertices. After subdividing edges, minimizing contagion essentially reduces to
IDM, albeit with additional restrictions on the vertices we can immunize (only
vertices that belong to the ”middle” of a subdivided edge can be deleted); we
therefore solve a generalization of the IDM problem, see Definition 10, and
use this to provide efficient algorithms for the problems we care about.

At a high-level, our algorithm works by solving the stopping contagion
recursively on subgraphs and then combining these solutions via dynamic-
programming until we have a solution for the whole graph. To combine
subproblems successfully, at each step we explicitly compute solutions for all
possible states of vertices in a bag. While this could take exponential time
in general, this approach provides an efficient algorithm in graphs with
bounded treewidth.

Our proof of bounded spread in noisy trees builds works by proving that small
subsets of such trees contain few edges [17, 30]. Since every non seed vertex
needs at least two vertices to get infected, small contagious sets require
small subsets that contain too many edges. Therefore, one can prove that small
sets of seeds cannot infect too many vertices; the proof of small trees’ local
sparsity is similar to the proof that w.h.p. such noisy trees have small local
treewidth.

###  2.5 Related work

While the idea to remove edges or vertices to contain an epidemic has been
studied before [51, 14, 3], most of these works focus using edge or vertex
deletions that break the graph to connected components of sublinear (or even
constant) size [25, 51, 14]. Recently approximation algorithms for edge
deletion problems that arise in controlling epidemics has been studied in [5]
for the SIR epidemic model. In particular, [5] studies the problem of deleting
a set of edges of weight at most $B$ that minimizes the set of infected nodes
after edges deletions. All these works consider a different contagion model
from the $r\geq 2$ bootstrap percolation model studied here.

Bootstrap percolation was first introduced by statistical physicists [15] and
has been studied on a variety of graphs such as grids [8], hypercubes [7, 45],
random graphs [30], graphs with a power law degree distribution [2, 55],
Kleinberg’s small world model [24] and trees [52].

The fixed parameter tractability of minimizing contagion with respect to
_vertex_ deletions, as opposed to edge deletions, has been thoroughly
investigated with respect to various parameters such as the maximum degree,
treewidth, and the size of the seed set $k$ in [18]. The authors of [18]
present efficient algorithms for minimizing contagion for graphs of bounded
maximum degree and treewidth. With respect to $k$, using ideas from FPT
algorithms for cut problems [31], they give a
$2^{k+\ell}\operatorname{poly}(n)$ algorithm for the case where the set of
seeds is of size $k$ and there is a solution of size $\ell$ to the problem.
Their algorithm can be easily adapted to the case of edge deletions: see
Theorem 13. We are not aware of the stopping contagion problem studied before,
nor are we aware of previous studies of the minimizing contagion problem in
random graphs. In order to deal with both stopping contagion and minimizing
contagion for graphs of bounded treewidth, we build on algorithmic ideas from
[11]. The NP-hardness of minimizing contagion with respect to vertex deletion
is proved in [18]—our proof for the NP-hardness of the edge deletion version
of minimizing contagion was found concurrently and independently; the proof is
different from the proof appearing in [18].

There are two regimes of interest for the study of treewidth in sparse random
graphs. For the subcritical regime $p\leq d/n$ with $d<1$, $G(n,p)$ has w.h.p.
unicyclic connected components of size $O(\log n)$ [28] and hence has
treewidth at most $2$. For the supercritical regime with $p\geq d/n$ and
$d>1$, $G(n,p)$ has w.h.p. a giant component of size $\Omega(n)$ [28] and
determining the treewidth is more complicated. Kloks [37] proved that the
treewidth of $G(n,d/n)$ is $\Omega(n)$ w.h.p. for $d\geq 2.36$. His result was
improved by Gao [33] who showed that for $d\geq 2.16$, the treewidth of
$G(n,d/n)$ is $\Omega(n)$ with high probability. Gao asked if his result can
be strengthened to prove that $G(n,d/n)$ has treewidth linear in $n$ w.h.p.
for any $d>1$; this was later shown in in [43]. A different and somewhat
simplified proof establishing that the treewidth of $G(n,d/n)$ is $\Omega(n)$
w.h.p. was given in [50]. Finally, the fine-grained behavior of treewidth of
$G(n,(1+\epsilon)/n)$ was studied in [22] where it was shown that for
sufficiently small $\epsilon$, the treewidth of $G(n,(1+\epsilon)/n)$ is
w.h.p.

$\displaystyle\Omega\left(\frac{\epsilon^{3}}{\log{1/\epsilon}}\right)n.$

The first lower bound for the treewidth of random regular graphs appears to be
from [50]: the authors prove that for every constant $d>d_{0}$ where $d_{0}$
is a sufficiently large constant, the treewidth of the random regular graph
$G(n,d)$ is $\Omega(n)$ w.h.p. In [29] it was also shown that random graphs
with a given degree sequence (with bounded maximum degree) that ensure the
existence of a giant component w.h.p. (namely a degree sequence satisfying the
Molloy-Reed criterion [44]) have linear treewidth as well, which implies,
using a different arguments from those in [50], that $G(n,d)$ for $d>2$ has
linear treewidth w.h.p. A different proof for the linear lower bound of the
treewidth of $G(n,d)$ for $d>2$ is given in [22].

Several papers have examined notions of local treewidth in devising algorithms
for algorithmic problems such as subgraph isomorphism [27, 35, 34, 32]. For
example, Grohe [34] defines a graph family $\mathcal{C}$ of having bounded
local treewidth if there exists a function $f:\mathbb{N}\rightarrow\mathbb{N}$
such that for every graph $G=(V,E)$ in $\mathcal{C}$ and every integer $r$,
for every vertex $v\in V$ the treewidth of the subgraph of $G$ induced on all
vertices of distance at most $r$ from $v$ is at most $f(r)$. These works
primarily focus on planar graphs and graphs avoiding a fixed minor. The only
work we are aware of that has examined the local treewidth of random graphs is
that of [23]. Their main goal is to demonstrate that the treewidth of balls of
radius $r$ around a given vertex depends only on $r$, as opposed to analyzing
the local treewidth as function of $n,d$ and $k$ as we do here. We employ a
similar edge excess argument to the one in [23] although there are some
differences in the analysis and the results: please see Section 3 for more
details. We are not aware of previous work lower bounding the local treewidth
of random graphs.

Embedding minors in expanders has received attention in combinatorics [42] and
theoretical computer science, finding applications in proof complexity [4].
Kleinberg and Rubinfeld [36] proved that if $G=(V,E)$ is a $\alpha$-vertex
expander with maximum degree $\Delta$, then every graph with
$n/\log^{\kappa}n$ vertices and edges is a minor of $G$ for a constant
$\kappa>1$ depending on $\Delta$ and $\alpha$. Later it was stated [16] that
$\kappa(\Delta,\alpha)=\Omega(\log^{2}(d)/\log^{2}(1/\alpha))$. Krivelevich
[40] together with Nandov proved that if $G$ is an $\alpha$-vertex expander
then it contains every graph with $cn/\log n$ edges and vertices for some
universal constant $c>0$.

The sparsity of random graphs as well as randomly perturbed trees was used in
showing that these families have w.h.p. bounded expansion555Bounded expansion
should not be confused with the edge expansion of a graph. For a precise
definition please see [47, 46]. [47, 20]. These results are incomparable with
our treewidth results: it is known that graphs with bounded maximum degree
have bounded expansion and that $G(n,d/n)$ has bounded expansion w.h.p. [47,
46] In contrast, there exist $3$-regular graphs with linear treewidth and as
previously mentioned the treewidth of $G(n,d/n)$ is $\Omega(n)$.

###  2.6 Future directions

Our work raises several questions. We consider undirected unweighted graphs.
However directed edges can be more accurate in modeling epidemic spread [1]
and some edges might be more costly to move than others. Extending our
algorithms to directed weighted graphs is an interesting direction for future
research.

Our upper and lower bounds for the local treewidth of $G(n,p)$ (with $p=d/n$)
currently differ by a multiplicative factor of order $\log d$. We believe that
for $k\leq n^{1-\epsilon}$ the local treewdith of $G(n,p)$ is w.h.p.
$\Omega(k\log d/\log n)$: whether this is indeed the case is left for future
work. Our upper bounds on the local treewidth of noisy trees can be made
independent of the maximum degree of the tree; namely, for arbitrary trees,
the local treewidth should be upper bounded w.h.p. by $O(k/\log n)$ assuming
$k$ is not too large. Proving or disproving this however remains open.
Understanding how well one can approximate minimizing contagion and stopping
contagion in general graphs, as well as graphs with certain structural
properties (e.g. planar graphs) is a potential direction for future research
as well. Finally, it could be of interest to study if our bounds for local
treewidth coupled with sophisticated algorithms for graphs with bounded local
treewidth [32, 34, 27] could lead to improved running time for additional
algorithmic problems in random graphs.

###  2.7 Organization

Our bounds regarding the local treewidth of $G(n,p)$ can be found in Section
3. Bounds for the local treewidth of noisy trees can be found in Section 4. A
high-level description of our algorithms for graphs of bounded treewidth can
be found in Section 5: Complete details and proofs can be found in the
Appendix. Our algorithms for random graphs and planar graphs can be found in
Section 6. Our bounds on the local treewidth and algorithms for planar and
random graphs are independent from one another: Understanding our algorithms
does not require delving into the the details of the proofs regarding bounds
on the local treewidth. Similarly, understating the algorithm for noisy trees
(Theorem 18) does not require reading the proofs of any of the Theorems or
Lemmas preceding Theorem 18 in Subsection 6.3.

###  2.8 Preliminaries

Throughout the paper $\log$ denotes the logarithm function with base $2$; we
omit floor and ceiling signs to improve readability. All graphs considered are
undirected and have no parallel edges. Given a graph $G=(V,E)$ and two
disjoint sets of vertices $A,B$ we denote by $E(A,B)$ the set of edges
connecting a vertex in $A$ to a vertex in $B$. For $A,B$ as above we denote by
$N_{G}(A,B)$ the set of vertices in $B$ with a neighbor in $A$. For a subset
of vertices $A\subseteq V$ and an edge $e$ we say that $A$ _touches_ $e$ if at
least one of the endpoints of $e$ belongs to $A$. If both endpoints of $e$
belong to $A$ then we say that $A$ _spans_ $e$.

A graph $H$ is a _minor_ of $G$ if $H$ can be obtained from $G$ by repeatedly
doing one of three operations: deleting an edge, contracting an edge or
deleting a vertex. We keep our graphs simple and remove any parallel edges
that may form during contractions. It can be verified [46] that a graph $H$
with $k$ vertices is a minor of $G$ if and only if there are $k$ vertex
disjoint connected subgraphs of $G,C_{1}\ldots C_{k}$ such that for every edge
$(v_{i},v_{j})$ of $H$, there is an edge connecting a vertex in $C_{i}$ to a
vertex of $C_{j}$. We refer to the map mapping every vertex of $H,v_{j}$ to
$C_{j}$ as an _embedding_ of $H$ in $G$; the maximum vertex cardinality of
$C_{i},1\leq i\leq k$ is called the _width_ of the embedding. We shall be
relying on the well-known fact [46, 21] that if $H$ is a minor of $G$ than the
treewidth of $G$ is lower bounded by the treewidth of $H$.

We will also need the following definition of an edge expander:

######  Definition 8.

Let $\alpha\in(0,1)$. A graph $G$ is an $\alpha$-expander if every subset of
vertices $S$ with $|S|\leq n/2$ satisfies

$|N_{G}(S,V\setminus S)|\geq\alpha|S|.$

##  3 Local treewidth of random graphs

In this section we prove both an upper and lower bound for $t_{k}(G(n,p))$
that with high probability. We assume $k\leq n^{1-\epsilon}$ for a constant
$\epsilon>0$.

###  3.1 Upper bound

Our main idea in upper bounding $t_{k}(G)$ is to leverage the fact that
$G(n,p)$ is locally sparse and that if a few edges are added on top of a tree,
the treewidth of the resulting graph cannot grow too much.

######  Lemma 1.

Let $G$ be a connected graph with $n$ vertices and $n-2+\ell$ edges. Then
$\operatorname{tw}(G)\leq\ell$.

###### Proof.

Since $G$ is connected, it must have a spanning tree $T$ with $n$ vertices and
$n-1$ edges. The graph $G$ has exactly $\ell-1$ additional edges; since adding
an edge can increase a graph’s treewidth by at most $1$, we immediately get
the desired bound.

$\displaystyle\operatorname{tw}(G)$
$\displaystyle\leq\operatorname{tw}(T)+\ell-1=\ell$

∎

We can now prove:

######  Theorem 6.

Suppose that $k\leq n^{1-\epsilon}$. Then for $G=G(n,p)$ we have that w.h.p.
for every $m\leq k$:

$\displaystyle t_{m}(G)\leq 3+O\left(\frac{m\log d}{\log n}\right).$

###### Proof.

Since the Theorem is obvious for $d=n^{\Omega(1)}$ we assume that $d\leq
n^{\epsilon/2}$. We first prove the statement for $m=k$. Given a graph $G$
with treewidth $t$, it is always possible to find a connected subgraph of $G$
with identical treewidth to $G$. In that spirit, rather than bounding the
probability there exists some $k$-vertex subgraph of $G$ with treewidth
exceeding some $r$, we bound the probability some subgraph on $s\leq k$
vertices is connected and has treewidth greater than $r$ in $G$.

Fix some $S\subseteq V$ with exactly $s$ vertices. Note there are $s^{s-2}$
possible spanning trees which could connect the vertices in $S$, each
requiring $s-1$ edges. While the resulting subgraph would be connected, its
treewidth is only $1$. Therefore, $r$ additional edges would also be required
to produce a subgraph with treewidth at least $r+1$. Accounting for the ways
to choose these edges, the probability the subgraph induced on $S$ is
connected and has treewidth greater than $r$ is at most

$\displaystyle
s^{s-2}\binom{\binom{s}{2}}{r}\left(\frac{d}{n}\right)^{r+s-1}.$

This follows since each edge occurs independently with probability $p=d/n$.
Now, we bound the probability that any such subset $S$ with at most $k$
vertices exists. To that end, we take a union bound over all $\binom{n}{s}$
possible subsets of $s$ vertices, letting $s$ range from $1$ to $k$. Putting
this together and using the inequality ${a\choose b}\leq(ea/b)^{b}$ yields

$\displaystyle\sum_{s=1}^{k}\binom{n}{s}\times
s^{s-2}\binom{\binom{s}{2}}{r}\left(\frac{d}{n}\right)^{r+s-1}$
$\displaystyle\leq\frac{d^{r}}{n^{r-1}}\sum_{s=1}^{k}e^{s}\left(\frac{es^{2}}{2r}\right)^{r}d^{s}$
$\displaystyle\leq\frac{d^{r}}{n^{r-1}}ke^{k}\left(\frac{ek^{2}}{r}\right)^{r}d^{k}$

To complete the proof, notice this probability can be made to be at most
$n^{-1}$ (using $k\leq n^{1-\epsilon}$ and $d\leq n^{\epsilon/2}$) when $r$ is
taken to be

$\displaystyle 2+O\left(\frac{k\log d}{\log n}\right).$

The Theorem now follows for $m=k$ from Lemma 1. Using the above proof along
with a simple union bound over all $m\leq k\leq n^{1-\epsilon}$ implies the
statement for all $m\leq k$. ∎

Notice the approach above yields a sharper bound than if we solely attempted
to bound the treewidth by counting the number of excess edges above $k-1$. To
explain, notice a $k$-vertex subgraph can have treewidth $r$ only if it has at
least $r+k-1$ edges. A simple union bound over all possible subsets of $k$
vertices, upper bounds the probability we are interested in.

$\displaystyle\binom{n}{k}\binom{\binom{k}{2}}{r+k-1}\left(\frac{d}{n}\right)^{r+k-1}\leq\frac{k^{2k}k^{2r}d^{k}d^{r}}{n^{r-1}}$

This is implicitly used in [23] to bound the treewidth of balls of radius $r$
in $G(n,p)$; as mentioned above, our method improves on this result. More
concretely, since the upper bound now has a additional $k^{k}$ factor in the
numerator, using this in our application would yield the weaker upper bound

$\displaystyle t_{k}(G)=3+O\left(\frac{k(\log k+\log d)}{\log n}\right).$

###  3.2 Lower bound

Throughout this section we assume that $d>1+\delta$ where $\delta>0$.

First we need the following result from [40]:

######  Proposition 1.

Consider the random graph $G:=G(n,\frac{1+\delta}{n}).$ Then there is a
constant $c>0$ depending on $\delta$ such that the following holds: For every
graph $H$ with at most $k\leq cn/\log n$ vertices and edges, $G$ contains an
embedding $H^{\prime}$ of $H$. Furthermore the width of the embedding is
$O(\log n)$.

######  Proposition 2.

There exist graphs with $m$ vertices and $m$ edges of treewidth $\Omega(m).$

###### Proof.

As random $3$-regular graphs have with high probability linear treewidth [22,
29] there are $m$-vertex graphs with $m$ vertices and $3m/2$ edges and
treewidth $\Omega(m)$. Adding to such a graph $m/2$ isolated vertices results
with a graph with the desired property. ∎

Using our results we can lower bound the local treewidth of a random graph:

######  Theorem 7.

Let $G:=G(n,d/n)$ be a random graph with $d>1+\delta$. Assume $k\leq O(n/\log
n)$. Then w.h.p. $G$ contains a subgraph with $O(k)$ vertices whose treewidth
is $\Omega(\frac{k}{\log n}).$

###### Proof.

We may assume that $k=\Omega(\log n)$, otherwise the lower bound in the
Theorem is immediate. Let $H$ be a graph with $s$ vertices and edges of
treewidth $\Omega(s)$ (Such a graph exists by proposition 2). Let
$s\leq\left(\frac{n}{\log n}\right)$. By Proposition 1, $G$ contains an
embedding of $H,H^{\prime}$ of width $O(\log n)$. It follows that $H^{\prime}$
has at most $O(s\log n)$ vertices and treewidth at least $\Omega(s)$ (as $H$
is a minor of $H^{\prime}$) which is what we wanted to prove. ∎

###  3.3 Local treewidth of random regular graphs

Similar bounds on the local treewidth of random regular graphs $G(n,d)$ can be
established via similar arguments to those used for $G(n,d/n).$ For the upper
bound, one can use the fact [17] that for every $k<nd/4$ distinct unordered
pairs of vertices, the probability they all occur simultaneously in $G(n,d)$
is at most $(2d/n)^{k}$ and then nearly identical arguments to those in
Theorem 6. The lower bound follows easily from embedding results for
expanders:

######  Theorem 8.

Let $d>2$ be a constant. Then with high probability a random $d$-regular graph
$G$ is minor universal: any graph $H$ with at most $O(n/\log n)$ vertices and
edges can embedded into $G$. Furthermore, the width of the embedding is
$O(\log n).$

###### Proof.

By a result of [40] if $G$ is an $\alpha$-expander with $\alpha>0$ bounded
away from zero then the claim in the Proposition hold. The result now follows
as it is well known [13, 38] that with high probability the random $d$-regular
graph is an $\alpha$-expander for $\alpha>0$. ∎

We summarize this with the following Theorem:

######  Theorem 9.

Suppose that $2<d$ is a constant and $k\leq n^{1-\epsilon}$ for some constant
$\epsilon\in(0,1)$ . Then for $G=G(n,d)$ we have that w.h.p.:

$\displaystyle\Omega\left(\frac{k}{\log n}\right)\leq t_{k}(G)\leq
3+O\left(\frac{k\log d}{\log n}\right).$

##  4 Local treewidth of noisy graphs

We study the local treewidth of noisy graphs: Recall that in this model there
is a base $n$-vertex graph $G$ with maximum degree $\Delta$. On top of this
base graph every non edge of $G$ is added independently with probability
$1/n$. All proofs missing from this section can be found in the Appendix. Our
main result is:

######  Theorem 10.

Let $G$ be an $n$-vertex connected graph of maximum degree $\Delta$. Suppose
that we add every non-edge of $G$ to $G$ with probability $1/n$ independently
of all other random edges. Call the resulting graph $G^{\prime}$. With high
probability, then, $t_{k}(G^{\prime})\leq O(t_{k}(G)+r)$, where

$\displaystyle r=3+O\left(\frac{k(\log k+\log\Delta)}{\log n}\right).$

To prove Theorem 10 we need several Lemmas. The first is due to [6]. While
tighter bounds are known [12], the simpler bound from [6] suffices to
establish our asymptotic upper bounds for the local treewidth.

######  Lemma 2.

Let $G$ be an $n$-vertex graph of maximum degree $\Delta$. Then the number of
connected subgraphs of $G$ with $k$ vertices is at most $n\Delta^{2(k-1)}$.

######  Lemma 3.

Suppose that we have a graph $H$ composed of $k$ connected components
$C_{1},\ldots,C_{k}$. Suppose that we merge these connected components by
adding exactly $k-1$ edges to produce a connected graph $G$. If
$t=\max\\{\operatorname{tw}(C_{1}),\ldots,\operatorname{tw}(C_{k})\\}$ then
the treewidth of $G$ is at most $\max\\{t,1\\}$.

###### Proof.

For connected components $C_{1},\dots,C_{k}$ consider tree decompositions
$T_{1},\allowbreak\dots,T_{k}$ with widths at most $t$; these surely exist
given the treewidth of each $C_{i}$ is at most $t$ for all $1\leq i\leq k$.

Assume $C_{i}$ and $C_{j}$ are connected in $G$ by an edge from vertex $v_{i}$
in $C_{i}$ to $v_{j}$ in $C_{j}$. Take the corresponding tree decompositions
$T_{i}$ and $T_{j}$ and choose arbitrary bags containing $v_{i}$ and $v_{j}$
respectively; introduce a new bag $\\{v_{i},v_{j}\\}$ and connect this to
both. Repeating this process for all $k-1$ edges added to $H$ connects all
$T_{1},\dots,T_{k}$. We claim the resulting graph is a valid tree
decomposition of $G$ with width at most $t$, proving the proposition.

Edge counting certifies the resulting connected graph is a tree. Furthermore,
every edge in $G$ has some bag containing its endpoints: edges from $H$ have
such a bag in some subtree $T_{i}$, while the remaining edges explicitly have
a bag with its endpoints as constructed above. Finally, since new bags
introduced share a vertex with each of its two neighbors, subgraphs
corresponding to individual vertices remain trees, satisfying the final
requirement for tree decompositions. ∎

Finally we need the following Lemma whose proof follows directly from the
handshake Lemma:

######  Lemma 4.

Let $G$ be a graph with average degree $d$, Then $G$ contains a subgraph $H$
of $G$ with $H$ having minimal degree at least $d/2$.

We can prove Theorem 10.

###### Proof.

We may assume $\Delta,k\leq n^{\epsilon}$ for sufficiently small $\epsilon$,
as otherwise the upper bound in the Theorem follows from the fact that
$t_{k}(G^{\prime})\leq k.$ We begin by upper bounding $t_{k}(G^{\prime})$ for
connected subgraphs of $G^{\prime}$ of size $k$. Later we show how to lift the
connectedness requirement. We consider two possibilities for $G$. In the
first, suppose all subgraphs of $G$ on $k$ vertices have at most

$\displaystyle\binom{k}{2}-(r+\ell-1)$

edges. Now fix such a subgraph $H$ of $G$ with $k$ vertices and $\ell\leq k$
connected components; we upper bound the probability the corresponding
subgraph $H^{\prime}$ in $G^{\prime}$ (the subgraph induced on the vertices of
$H$ in $G^{\prime}$) is connected and has treewidth at least $t_{k}(G)+r$.

To that end, the probability a fixed set of $\ell-1$ random edges connect the
$\ell$ connected components in $H$ into a single component in $G^{\prime}$ is
$n^{-(\ell-1)}$.

By construction, the largest component in $H$ has size no larger than
$k-\ell+1$. Therefore, by our lemma, the treewidth of $H$ together with
$\ell-1$ connecting edges is upper bounded by $t_{k-\ell+1}(G)$. For
$H^{\prime}$ to additionally have treewidth at least $t_{k}(G)+r$, a minimum
of $r$ additional random edges must be present in $H$ as $t_{k-\ell+1}(G)\leq
t_{k}(G)$. Therefore, we can upper bound the probability that $H^{\prime}$ is
both connected and has treewidth larger than $r$ by

$\displaystyle\binom{k^{2}}{r+\ell-1}n^{-(r+\ell-1)}$

We count the number of possible subgraphs $H$ with $k$ vertices and $\ell$
connected components. An upper bound can be derived by noticing there are
$\binom{k-1}{\ell-1}$ ways to choose the positive sizes of the components,
denoted $s_{1},\dots,s_{\ell}$. For each set of sizes, we can bound the
choices of components using Lemma 2:

$\displaystyle\prod_{i=1}^{\ell}n\Delta^{2(s_{i}-1)}$ $\displaystyle\leq
n^{\ell}\Delta^{2\sum_{i=1}^{\ell}s_{i}}=n^{\ell}\Delta^{2k}.$

We can now upper bound the probability there exists some $k$-vertex subgraph
of $G$, $H$, whose corresponding subgraph in $G^{\prime}$ is connected and has
treewidth at least $t_{k}(G)+r$, denoted $p(n,\Delta,k,r)$. Since $G$ is
connected, this is equivalent to the probability $t_{k}(G^{\prime})\geq
t_{k}(G)+r$. Now take a union bound over all possible subgraphs $H$ on $k$
vertices and $1\leq\ell\leq k$ connected components; in particular, for each
possible choice of $\ell$, we multiply an upper bound on the number of
possible subgraphs by the maximum probability each subgraph ends up connected
and with large treewidth, derived above. Applying the inequality
$\binom{q}{s}\leq q^{s}$, we arrive at the following upper bound:

$\displaystyle p(n,\Delta,k,r)$
$\displaystyle\leq\sum_{\ell=1}^{k}\binom{k-1}{\ell-1}n^{\ell}\Delta^{2k}\times\binom{k^{2}}{r+\ell-1}n^{-(r+\ell-1)}$
$\displaystyle\leq\frac{k^{2(r+k)}\Delta^{2k}}{n^{r-1}}\sum_{\ell=1}^{k}k^{\ell}$
$\displaystyle\leq\frac{k^{2r}\Delta^{2k}}{n^{r-1}}k^{3k+1.}$

Taking logarithms and using our assumptions on $k,\Delta$ we have that for

$r=O\left(\frac{k(\log k+\log\Delta)}{\log n}\right)$

it holds that $p(n,\Delta,k,r)\leq O(1/n).$

Now consider the second case where $G$ has some some $k$-vertex subgraph $H$
with $\ell\leq k$ connected components and more than

$\displaystyle\binom{k}{2}-(r+\ell-1)\geq{k\choose 2}-2k+1$

edges. We may assume without loss of generality that $r\leq k$, as otherwise
the inequality $t_{k}(G^{\prime})\leq O(t_{k}(G)+r)$ trivially holds—in fact,
$t_{k}(G^{\prime})\leq r$. Given its edge count $H$ has average degree
$\Omega(k)$. It follows from Lemma 4 that $H$ contains a subgraph $\tilde{H}$
of minimum degree $\Omega(k)$. Therefore $\tilde{H}$, and hence $H$, have
treewidth $\Omega(k)$, since any graph of treewidth $w$ must contain a vertex
of degree at most $w$. Hence, we get that $t_{k}(G^{\prime})\leq
O(t_{k}(G)+r)$ as $t_{k}(G^{\prime})\leq k$; in fact, $t_{k}(G^{\prime})\leq
O(t_{k}(G))$ in this case.

To conclude the proof we need to consider $k$-vertex subgraphs of $G^{\prime}$
that are not necessarily connected. To prove our claim for subgraphs that are
not connected, we need to consider their connected components. As we have
shown, the probability there is a connected subgraph with $k^{\prime}$
vertices for a fixed $k^{\prime}<k$ with treewidth larger than
$t_{k}^{\prime}(G)+O(r(k^{\prime},n,\Delta)$ is $O(1/n)$. Therefore a simple
union bounded argument over all $k^{\prime}\leq k$ (using $k\leq
n^{\epsilon}$) as well as the fact that the treewidth of a graph with
components $C_{1}\ldots C_{j}$ is
$\max(\\{\operatorname{tw}(C_{1})\ldots\operatorname{tw}(C_{j})\\})$ concludes
the proof. ∎

Observe that similarly to the $G(n,d/n)$ case, a simple union bound argument
implies that w.h.p $t_{s}(G^{\prime})\leq O(t_{s}(G)+r)$ for all $s\leq k.$

Finally, the upper bound in Theorem 10 is nearly tight for certain noisy
trees.

######  Theorem 11.

Consider the $n$ vertex path, $P_{n}$. Suppose we add every nonedge to $P_{n}$
with probability $\epsilon/n$ where $\epsilon>0$ is an arbitrary constant.
Call the perturbed graph $P^{\prime}.$ Then with high probability for any
$\Omega(\log n)\leq k\leq O(n/\log n)$, there exists a subgraph of
$P^{\prime}$ with $O(k)$ vertices with treewidth $\Omega(k/\log n).$

###### Proof.

Fix $B$ to be a large enough constant. Chop $P_{n}$ to $n/B$ disjoint
paths666To simplify the presentation we assume $B$ divides $n$. Similar ideas
work otherwise. $A_{1}\ldots A_{n/b}$ each of length $B$. Consider now the
graph $G$ whose vertex set is $A_{1}\ldots A_{n/B}$ and two vertices $A_{i}$
and $A_{j}$ are connected if there is an edge (in $P^{\prime}$) connecting
$A_{i}$ to $A_{j}$. The probability two vertices in $G$ are connected is at
least

$1-\left(1-\epsilon/n\right)^{B^{2}}\geq\epsilon B^{2}/2n.$

For a fixed graph $H$ with $s$ vertices and edges, it is known [40] that the
supercritical random graph $G(m,\frac{1+\epsilon}{m})$ contains an embedding
of $H$ into $G$ as long as $s=O(m/\log m)$. Furthermore the width of the
embedding is $O(\log m)$. The probability that two vertices in $G$ are
connected is larger than $\frac{1+\epsilon}{n/B}$. Therefore we can embed $H$
into a subgraph $H^{\prime}$ of $G$ whose size is at most $s\log n$ such that
$H$ is a minor of $H^{\prime}$. Furthermore as the vertices of $G$ are paths
of length $B$ (in $P_{n}$), the embedding of $H$ into $G$ directly translates
to an embedding of $H$ into $P^{\prime}$ whose width is $O(B\log n)=O(\log
n)$. Choosing $H$ with $s$ vertices and edges and treewidth $\Omega(s)$
concludes the proof. ∎

##  5 Algorithms for graphs of bounded treewidth

In this section, we build on the results of [18] to provide polynomial time
algorithms for bounded treewidth instances of minimizing contagion and
stopping contagion. As we sketched in our introduction, we generalize the
influence diffusion minimization problem introduced by the authors and use a
similar dynamic-programming algorithm. Our main result is the following
algorithm for graphs of bounded treewidth $\tau$:

######  Theorem 12.

Let $G$ be an $n$ vertex graph with maximum degree $\Delta$, maximum threshold
$r$ and treewidth $\tau$. Then both minimizing and stopping contagion can be
solved in time $O\left(\tau
1296^{\tau}\min\\{r,\max\\{\Delta,2\\}\\}^{4\tau}\operatorname{poly}(n)\right)$.

For a proof, including a description of our algorithm and runtime analysis,
please see the Appendix. Note that to combine subproblems, we must effectively
account for the effect of infected vertices elsewhere on each subgraph we
consider. We therefore essentially solve minimizing contagion and stopping
contagion in a more flexible infection model, where thresholds are allowed to
differ between vertices but remain at most $r$; as a result, our theorem
cleanly translates to this setting as well.

##  6 Algorithms for minimizing and stopping contagion in grids, random graphs
and noisy trees

In this section we study how to solve minimizing contagion and stopping
contagion when the set of seeds $A$ is not too large and does not spread by
too much. We use this along with local treewidth upper bounds to devise
algorithms for minimizing and stopping contagion in random graphs. We also
consider algorithms for grids and planar graphs. As usual all missing proofs
appear in the Appendix.

Using similar ideas to [18] (who consider vertex deletions problems) we have
the following result for the minimizing contagion problem.

######  Theorem 13.

Let $G=(V,E)$ be an $n$-vertex graph. Suppose there are $t$ edges whose
removal ensures no more than $r$ vertices are infected in $G$ from the seed
set $A\subseteq V$. Then minimizing contagion can be solved optimally in
(randomized) $2^{r+t}\operatorname{poly}(n)$ time where $n$ is the number of
vertices.

###### Proof.

Color every vertex in $V\setminus A$ independently blue or red. Consider a
solution of $t$ edges such that after removing these edges a set $B$ of
cardinality at most $r$ is infected from $A$. With probability at least
$2^{-r}$ all vertices in $B$ are red. For each of the $t$ edges in an optimal
solution, exactly one endpoint does not get infected from $A$ as a result of
removing the edge. With probability at least $2^{-t}$, all these $t$ endpoints
belonging to edges in an optimal solution are colored blue. Assuming the two
events above occur, we run the contagion process only on red vertices and find
the set of vertices $B$ infected from $A$. Once we recover $B$ we can remove
the minimum set of edges from $G$ ensuring only $B$ is infected from $A$.
Therefore we can solve the problem optimally with probability (at least)
$2^{-(t+r)}$. Repeating this process independently $2^{r+t+10}$ times results
with a randomized algorithm solving this problem with probability at least
$2/3$. The running time is $2^{r+t}\operatorname{poly}(n)$ as desired. ∎

The algorithm above can become slow if $r$ or $t$ are very large.
Additionally, we do not know how to get similar results (e.g., algorithms of
running time $2^{|A|}\operatorname{poly}(n)$) for stopping contagion. Below we
show that we can improve upon this algorithm for graphs that have some local
sparsity conditions. A key property we use is that for both minimizing
contagion and stopping contagion with a seed set $A,$ we restrict our
attention to the subgraph of $G$ induced on $\langle A\rangle$.

###  6.1 Grids and planar graphs

Consider the $n\times n$ grid where all vertices have threshold at least 2 we
have the following “bounded spread” result:

######  Lemma 5.

In the $n\times n$ grid every set of size $k$ infects no more than $O(k^{2})$
vertices.

###### Proof.

Embed the $n\times n$ grid $G=\\{1,\ldots,n\\}\times\\{1,\ldots,n\\}$ in
$H=\\{0,\ldots,n+1\\}\times\\{0,\ldots,n+1\\}$ in the natural way. Given a
subset $A$ of $G$, the _perimeter_ of $A$ is the set of all vertices not
belonging to $A$ having a neighbor in $A$. The crucial observation is that if
$A$ is a set of infected seeds, the perimeter of $A$ can never increase during
the contagion process [9]. As the perimeter of $A$ is at most $4k$ the
infected set has perimeter at most $4k$ as well. The result follows as every
set $A\subseteq\\{1,\ldots,n\\}\times\\{1,\ldots,n\\}$ of size $m$ has
perimeter $\Omega(\sqrt{m})$. ∎

Using Theorem 13 we have that minimizing contagion on the $n$ by $n$ grid with
$k=|A|$ can be solved in time $2^{O(k^{2})}\operatorname{poly}(n)$. We simply
apply the algorithm in Theorem 13 to $\langle A\rangle$. Alternatively we can
use exhaustive search over all subsets of edges in the graph induced on
$\langle A\rangle$ to solve777For minimizing contagion using the FPT algorithm
may be preferable as it may run significantly faster if the optimal solution
has cardinality $o(k^{2})$. both minimizing or stopping contagion. We can do
better using the following fact:

######  Lemma 6.

Let $G$ be a subgraph of an $n$ by $n$ grid with $r$ vertices. Then $G$ has
treewidth $O(\sqrt{r})$.

###### Proof.

Every $m$-vertex planar graph has treewidth $O(\sqrt{m})$. ∎

We get:

######  Corollary 1.

Let $G=(V,E)$ be the $n$ by $n$ grid. Suppose $H=(V,E^{\prime})$ where
$E^{\prime}\subseteq E$ and every vertex has a threshold of at least $2$. Let
$A$ be the seed set with $k=|A|.$ Then stopping contagion and minimizing
contagion can be solved in time $2^{O(k)}\operatorname{poly}(n)$.

###### Proof.

For solving either problems we only need to consider the subgraph of
$G,\langle A\rangle$. The result now follows from Theorem 12. ∎

Similarly, for a planar graph where every vertex has threshold at least $2$
and at most $b$ and every subset $A$ of size $k$ infects at most $f(k)$
vertices, stopping contagion can be solved in time
$b^{O(\sqrt{f(k)})}\operatorname{poly}(n)$.

###  6.2 Sparse random graphs

Consider the random graph $G(n,d/n)$ assuming all vertices have threshold
larger than $1$. Assuming $d\leq n^{1/2-\delta}$ for $\delta\in(0,1/2)$, it is
known [30] that with high probability every set of size $O(\frac{n}{d^{2}\log
d})$ does not infect more than $O(|A|\log d)$ vertices. Furthermore, it is
known [30] that any set of size $O(n/d^{2})$ has with high probability
constant average degree. It follows that assuming $|A|=O(\frac{n}{d^{2}\log
d})$ the optimal solution to minimizing contagion is of size $O(|A|\log d)$.
Therefore in random graphs with $|A|\leq O(\frac{n}{d^{2}\log d})$, minimizing
contagion can be solved using Theorem 13 in time $O(2^{|A|\log
d}\operatorname{poly}(n))$. As before, exhaustive search over all edges on the
graph induced on $\langle A\rangle$ can solve both minimizing and stopping
contagion in time $O(2^{|A|\log d}\operatorname{poly}(n))$ as well.

Using our local treewidth estimates, Theorem 12, the bounded spread property
and the fact that w.h.p the maximum degree of $G$ is $O(\log n/\log\log n)$ we
have the following improvement for the running time:

######  Theorem 14.

Let $G:=G(n,d/n),\epsilon\in(0,1)$ and $\delta\in(0,1/2)$. Denote by $k$ to be
the size of the seed set $A$. Suppose that $k\leq
O(\min(n^{1-\epsilon},\frac{n}{d^{2}\log d}))$ and $d\leq n^{1/2-\delta}$, and
that every vertex has threshold larger than $1$. Then w.h.p both minimizing
contagion and stopping contagion can be solved in time

$\exp\left(O\left(\frac{k\log^{2}d\log\log n}{\log
n}\right)\right)\operatorname{poly}(n).$

###### Proof.

As before we can solve either problem on $\langle A\rangle$ using the upper
bound on the treewidth from Theorem 6, the fact that with high probability
$|\langle A\rangle|\leq O(\log d|A|)$ and the algorithm for graphs of bounded
treewidth for stopping or minimizing contagion. ∎

One can derive similar algorithms for stopping contagion in random $d$-regular
graphs (where $d$ is a constant). As the details are very similar to the
analysis of the binomial random graph they are omitted.

###  6.3 Noisy trees

We now devise an algorithm for stopping contagion and minimizing contagion for
noisy trees. To achieve this we first prove that for forests every sets of
seeds does not spread by much and furthermore this property is maintained
after adding a ”small” number of edges on top of the edges belonging to the
forest. Then we use similar ideas to Theorem 10 and prove that noisy trees are
locally sparse in the sense that every subsets of vertices of cardinality $k$
spans w.h.p $k+o(k)$ edges assuming $k$ is not too large. We use this property
to prove that any subset $A$ of $k$ seeds infects w.h.p $O(k)$ vertices.
Thereafter we can use the algorithms for bounded treewidth to solve either
minimizing contagion or stopping contagion on $\langle A\rangle$. We assume
throughout this section that $\epsilon\in(0,1)$ is a sufficiently small
constant ($\epsilon<1/100$ would suffice for our proofs to go through).

Let $T$ be an $n$-vertex tree with max degree $\Delta$ and let $T^{\prime}$ be
the noisy tree obtained from $T$. Here we show that with high probability
every set of $k\leq n^{\epsilon}$ seeds does not infect more than $ck$
additional nodes where $c$ is an absolute constant. One key ingredient is
proving that such noisy trees are locally sparse.

######  Theorem 15.

Let $T$ be a tree of maximum degree $\Delta$ and let $T^{\prime}$ be the noisy
graph obtained from $T$. Suppose $k,\Delta\leq n^{\epsilon}$. Then with high
probability every set of $k$ seeds infects no more than $ck$ vertices where
$c$ is some absolute constant.

We need a few preliminaries before we can prove Theorem 15.

When $T$ is a tree, a subset of vertices with $k$ vertices and $\ell$
components spans exactly $k-\ell$ edges. A simple modification of the proof of
Theorem 10 yields:

######  Theorem 16.

Let $T^{\prime}$ be the noisy tree. Then, with probability $1-O(1/n)$, every
connected subset of vertices of size $k$ in $T^{\prime}$ spans at most

$\displaystyle(k-1)+1+O\left(\frac{k(\log k+\log\Delta)}{\log n}\right)$

edges.

###### Proof.

First observe that if $k$ or $\Delta$ are larger than $n^{\Omega(1)}$ the
statement in the Theorem follows immediately from the fact that in $G(n,1/n)$
w.h.p every subset $|S|$ of vertices spans at most $2|S|$ edges [41]. Hence we
shall assume that $\Delta,k\leq n^{\epsilon}.$ We employ a nearly identical
argument to that used in the proof of Theorem 10. Here, we are interested in
bounding the probability some $k$-vertex subgraph of $T$ ends up connected in
$T^{\prime}$ with at least $k-1+r$ edges.

Now fix such a $k$-vertex subgraph of $T$ with $\ell$ connected components,
$H$. Since $T$ is a tree, any such subgraph will contain exactly $k-\ell$
edges; $\ell-1$ random edges will be required to connect $H$ and $r$
additional to reach the $k-1+r$ edge threshold. As argued in the proof of
Theorem 10, this happens with probability upper bounded by

$\displaystyle\binom{k^{2}}{r+\ell-1}n^{-(r+\ell-1)}$

We can now take a union bound over all possible subgraphs (of $T$) on $k$
vertices and $1\leq\ell\leq k$ connected components in $T$; this yields the
same upper bound on the probability $T^{\prime}$ contains a connected subgraph
with more than $k+r$ edges computed in the proof of Theorem 10:

$\displaystyle\frac{k^{2r}\Delta^{2k}}{n^{r-1}}k^{3k+1.}$

Setting $r$ as in the claim ensures the probability some $k$-vertex connected
subgraph in $T^{\prime}$ has at least $k+r$ edges is $O(1/n)$, as desired. ∎

We now easily extend this argument to all connected subgraphs of size at most
$k$ in $T^{\prime}$, rather than simply those size exactly $k$.

######  Corollary 2.

Let $T,T^{\prime}$ be as in Theorem 16. Suppose $t=n^{\epsilon}$. Then w.h.p
every connected subgraph of $T^{\prime}$ with $k\leq t$ vertices has at most

$\displaystyle(k-1)+1+O\left(\frac{k(\log k+\log\Delta)}{\log n}\right)$

edges.

###### Proof.

From Theorem 16, we know the probability that some connected subgraph on $k$
vertices exceeds this number of edges is $O(1/n)$. Taking a union bound over
all $k\leq t$ concludes the proof. ∎

We can now prove:

######  Theorem 17.

Let $T,T^{\prime},k$ be as in Theorem 16. Then, w.h.p every subset of vertices
of size $k$ in $T^{\prime}$ spans at most

$\displaystyle(k-1)+1+O\left(\frac{k(\log k+\log\Delta)}{\log n}\right)$

edges.

###### Proof.

The result Theorem 16 extends to arbitrary (not necessarily connected)
subgraphs of $T^{\prime}$ by decomposing an arbitrary subgraph with $k$
vertices of $F$ to its $\ell$ connected components with sizes
$k_{1}+\dots+k_{\ell}=k$. Applying the bound derived above to each of these
connected subgraphs, we know that for some constants $c_{1},\dots c_{\ell}$,
we have that with high probability for $C=\max(c_{1}\ldots c_{\ell})$:

$\displaystyle\sum_{i=1}^{\ell}\left[(k_{i}-1)+1+c_{i}\frac{k_{i}(\log
k_{i}+\log\Delta)}{\log n}\right]$ $\displaystyle\leq k+\frac{C}{\log
n}\sum_{i=1}^{\ell}k_{i}\log k_{i}+C\frac{k\log\Delta}{\log n}$
$\displaystyle\leq k+\frac{C}{\log n}k\log k+C\frac{k\log\Delta}{\log n}$
$\displaystyle=(k-1)+1+O\left(\frac{k(\log k+\log\Delta)}{\log n}\right).$

The second inequality follows from rewriting $\log k_{i}$ as $\log
k-\log(k/k_{i})$ and collecting the positive terms. This concludes the proof.
∎

As before it is easy to extend the Theorem above to all subsets of
$T^{\prime}$ of size at most $k$. Details omitted.

We proceed to prove the bounded spread property of noisy trees. We need a few
more auxiliary Lemmas.

######  Lemma 7.

Let $G$ be a forest. Suppose the threshold of every vertex is at least $2$.
Then any set of $k$ seeds in $G$ activates less than $k$ additional vertices
in $G$.

###### Proof.

If a set of seeds $A$ activates a set $B$ of additional vertices then
$|E(A\cup B)|\geq 2|B|$ as every vertex in $B$ must be adjacent to two active
vertices. On the other hand, as $G$ is a forest we have that $|E(A\cup
B)|\leq|A|+|B|-1$. Therefore $|B|<|A|$ which is what we wanted to prove. ∎

######  Lemma 8.

Let $G$ be a graph and suppose we add a set of $k$ edges to $G$. Call the
resulting graph $H$. Then $m(H,2)\geq m(G,2)-k$.

###### Proof.

Suppose towards contradiction that $m(H,2)<m(G,2)-k$. Consider a contagious
set $A$ in $H$ of minimal size. $A$ can be turned into a contagious set in $G$
by adding no more than $k$ vertices: we run the contagious process on $G$ and
whenever we reach a vertex that was infected from $A$ (in $H$) because of an
additional edge in $H$ we simply add it to $A$. The total number of vertices
added in this way is at most $k$. Therefore, if $m(H,2)<m(G,2)-k$ we would
have found a contagious set in $G$ of size smaller than $m(G,2)$ which is
absurd. ∎

Lemmas 7 and 8 easily extend to the case where the threshold of every vertex
is at least 2.

We can now prove Theorem 15.

###### Proof.

We prove the result for the case every vertex has threshold exactly $2$. The
result when the thresholds are at least $2$ is similar. Consider a set $A$ of
$k$ seeds. Suppose $A$ infects an additional set of vertices $B$. We now show
that w.h.p for a large enough constant $c,$ $|B|$ must be smaller than $c|A|$.
Else, suppose that $A$ infects at least $c|A|$ vertices for some fixed
constant $c$. Without loss of generality $A$ infects exactly $c|A|$ additional
vertices. Assuming that $c$ is sufficiency large, we have using Theorem 16
that w.h.p the number of edges in $T^{\prime}$ added on top of $F$, the
subgraph of $T$ induced on $A\cup B$ is smaller than $(|A|+|B|)/4$. In
addition, $F$ satisfies by Theorem 16 the inequality $m(F,2)\geq(|A|+|B|)/2$.
Therefore, by Lemma 8, in $T^{\prime}$ the subgraph $F^{\prime}$ induced on
$A\cup B$ satisfies w.h.p. $m(F^{\prime},2)\geq(|A|+|B|)/4$. On the other
hand, we have that $m(F^{\prime},2)\leq|A|$ as we assume $A$ infects $B$ in
$F^{\prime}$. Taking $c>3$ leads to a contradiction concluding the proof. ∎

As the star with $n-1$ leafs shows, the spread of a subset of size $2$ in a
noisy tree with degree $\Omega(n)$ can be w.h.p $\Omega(\log n).$ In addition,
we believe that this is the worst possible spread: every subset of size $k$ in
a noisy tree will not infect with high probability more than $O(k\log n)$
vertices. It seems likely that that restriction on $k$ in Theorem 15 can be
lifted and that the Theorem holds for arbitrary $k$. Whether this is the case
is left for future work.

Finally, we can leverage Theorem 15 to get algorithms for stopping contagion
in noisy trees:

######  Theorem 18.

Let $T$ be a tree and let $T^{\prime}$ be the noisy tree obtained from $T$.
Assume $|A|=k,\Delta\leq n^{\epsilon}$ and that every vertex has threshold
larger than $1$. Let $m:=\max(\log\log n,\log\Delta)$. Then both minimizing
contagion and stopping contagion can be solved in $T^{\prime}$ in time

$\exp\left(O\left(\frac{k(\log k+\log\Delta)m}{\log
n}\right)\right)\operatorname{poly}(n).$

###### Proof.

This follows the fact that w.h.p $|\langle A\rangle|=O(k)$, the upper bound on
the treewidth of the subgraph induced on $\langle A\rangle$ from 10, Theorem
12 and the fact that the maximum degree of $G(n,1/n)$ is $O(\log n/\log\log
n)$ with high probability. ∎

## Acknowledgements

We are very grateful to Michael Krivelevich 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 helpful comments and
suggestions. In particular we thank a reviewer for noting a gap in a claimed
proof of a stronger lower bound of $\Omega(k\log d/\log n)$ of the local
treewidth of $G(n,d/n)$.

An inspiration for this paper has been the operation of the Oncology
department at Haddasah Ein Karem hospital during the Covid-19 pandemic. Their
professionalism and dedication are greatly acknowledged.

## References

  * [1] Antoine Allard, Cristopher Moore, Samuel V Scarpino, Benjamin M Althouse, and Laurent Hébert-Dufresne.  The role of directionality, heterogeneity and correlations in epidemic risk and spread.  arXiv preprint arXiv:2005.11283, 2020.
  * [2] Hamed Amini and Nikolaos Fountoulakis.  Bootstrap percolation in power-law random graphs.  Journal of Statistical Physics, 155(1):72–92, 2014.
  * [3] James Aspnes, Kevin Chang, and Aleksandr Yampolskiy.  Inoculation strategies for victims of viruses and the sum-of-squares partition problem.  Journal of Computer and System Sciences, 72(6):1077–1093, 2006\.
  * [4] Per Austrin and Kilian Risse.  Perfect matching in random graphs is as hard as tseitin*.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 979–1012. SIAM, 2022.
  * [5] Amy Babay, Michael Dinitz, Aravind Srinivasan, Leonidas Tsepenekas, and Anil Vullikanti.  Controlling epidemic spread using probabilistic diffusion models on networks.  arXiv preprint arXiv:2202.08296, 2022.
  * [6] Amitabha Bagchi, Ankur Bhargava, Amitabh Chaudhary, David Eppstein, and Christian Scheideler.  The effect of faults on network expansion.  Theory of Computing Systems, 39(6):903–928, 2006.
  * [7] József Balogh and Béla Bollobás.  Bootstrap percolation on the hypercube.  Probability Theory and Related Fields, 134(4):624–648, 2006.
  * [8] József Balogh, Béla Bollobás, Hugo Duminil-Copin, and Robert Morris.  The sharp threshold for bootstrap percolation in all dimensions.  Transactions of the American Mathematical Society, 364(5):2667–2701, 2012.
  * [9] József Balogh and Gábor Pete.  Random disease on the square grid.  Random Structures & Algorithms, 13(3-4):409–422, 1998.
  * [10] Luca Becchetti, Andrea Clementi, Riccardo Denni, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi.  Sharp thresholds for a sir model on one-dimensional small-world networks.  arXiv preprint arXiv:2103.16398, 2021.
  * [11] Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, and Ilan Newman.  Treewidth governs the complexity of target set selection.  Discrete Optimization, 8(1):87–96, 2011.
  * [12] Andrew Beveridge, Alan Frieze, and Colin McDiarmid.  Random minimum length spanning trees in regular graphs.  Combinatorica, 18(3):311–333, 1998.
  * [13] Béla Bollobás.  The isoperimetric number of random regular graphs.  European Journal of combinatorics, 9(3):241–244, 1988.
  * [14] Alfredo Braunstein, Luca Dall’Asta, Guilhem Semerjian, and Lenka Zdeborová.  Network dismantling.  Proceedings of the National Academy of Sciences, 113(44):12368–12373, 2016.
  * [15] John Chalupa, Paul L Leath, and Gary R Reich.  Bootstrap percolation on a bethe lattice.  Journal of Physics C: Solid State Physics, 12(1):L31, 1979.
  * [16] Julia Chuzhoy and Rachit Nimavat.  Large minors in expanders.  arXiv preprint arXiv:1901.09349, 2019.
  * [17] Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, and Daniel Reichman.  Contagious sets in expanders.  In Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms, pages 1953–1987. SIAM, 2014.
  * [18] Gennaro Cordasco, Luisa Gargano, and Adele Anna Rescigno.  Parameterized complexity of immunization in the threshold model.  arXiv preprint arXiv:2102.03537, 2021.
  * [19] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized algorithms, volume 5.  Springer, 2015.
  * [20] Erik D Demaine, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar, and Blair D Sullivan.  Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs.  arXiv preprint arXiv:1406.2587, 2014.
  * [21] Reinhard Diestel.  Graph theory 3rd ed.  Graduate texts in mathematics, 173, 2005.
  * [22] Tuan Anh Do, Joshua Erde, and Mihyun Kang.  A note on the width of sparse random graphs.  arXiv preprint arXiv:2202.06087, 2022.
  * [23] Jan Dreier, Philipp Kuinke, Ba Le Xuan, and Peter Rossmanith.  Local structure theorems for erdős–rényi graphs and their algorithmic applications.  In International Conference on Current Trends in Theory and Practice of Informatics, pages 125–136. Springer, 2018.
  * [24] Roozbeh Ebrahimi, Jie Gao, Golnaz Ghasemiesfeh, and Grant Schoenebeck.  Complex contagions in kleinberg’s small world model.  In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 63–72, 2015.
  * [25] Jessica Enright and Kitty Meeks.  Deleting edges to restrict the size of an epidemic: a new application for treewidth.  Algorithmica, 80(6):1857–1889, 2018.
  * [26] Jessica Enright, Kitty Meeks, George B Mertzios, and Viktor Zamaraev.  Deleting edges to restrict the size of an epidemic in temporal networks.  Journal of Computer and System Sciences, 119:60–77, 2021.
  * [27] David Eppstein.  Subgraph isomorphism in planar graphs and related problems.  In Graph Algorithms and Applications I, pages 283–309. World Scientific, 2002.
  * [28] Paul Erdős, Alfréd Rényi, et al.  On the evolution of random graphs.  Publ. Math. Inst. Hung. Acad. Sci, 5(1):17–60, 1960.
  * [29] Uriel Feige, Jonathan Hermon, and Daniel Reichman.  On giant components and treewidth in the layers model.  Random Structures & Algorithms, 48(3):524–545, 2016.
  * [30] Uriel Feige, Michael Krivelevich, Daniel Reichman, et al.  Contagious sets in random graphs.  The Annals of Applied Probability, 27(5):2675–2697, 2017.
  * [31] Fedor V Fomin, Petr A Golovach, and Janne H Korhonen.  On the parameterized complexity of cutting a few vertices from a graph.  In International Symposium on Mathematical Foundations of Computer Science, pages 421–432. Springer, 2013.
  * [32] Markus Frick and Martin Grohe.  Deciding first-order properties of locally tree-decomposable structures.  Journal of the ACM (JACM), 48(6):1184–1206, 2001.
  * [33] Yong Gao.  Treewidth of erdős–rényi random graphs, random intersection graphs, and scale-free random graphs.  Discrete Applied Mathematics, 160(4-5):566–578, 2012.
  * [34] Martin Grohe.  Local tree-width, excluded minors, and approximation algorithms.  Combinatorica, 4(23):613–632, 2003.
  * [35] Mohammad Taghi Hajiaghayi.  Algorithms for graphs of (locally) bounded treewidth.  PhD thesis, Citeseer, 2001.
  * [36] Jon Kleinberg and Ronitt Rubinfeld.  Short paths in expander graphs.  In Proceedings of 37th Conference on Foundations of Computer Science, pages 86–95. IEEE, 1996.
  * [37] Ton Kloks.  Treewidth: computations and approximations.  Springer, 1994.
  * [38] Brett Kolesnik and Nick Wormald.  Lower bounds for the isoperimetric numbers of random regular graphs.  SIAM Journal on Discrete Mathematics, 28(1):553–575, 2014.
  * [39] Michael Krivelevich.  Finding and using expanders in locally sparse graphs.  SIAM Journal on Discrete Mathematics, 32(1):611–623, 2018.
  * [40] Michael Krivelevich.  Expanders – how to find them, and what to find in them.  Surveys in Combinatorics, 456:115–142, 2019.
  * [41] Michael Krivelevich, Daniel Reichman, and Wojciech Samotij.  Smoothed analysis on connected graphs.  SIAM Journal on Discrete Mathematics, 29(3):1654–1669, 2015.
  * [42] Michael Krivelevich and Benjamin Sudakov.  Minors in expanding graphs.  Geometric and Functional Analysis, 19(1):294–331, 2009.
  * [43] Choongbum Lee, Joonkyung Lee, and Sang-il Oum.  Rank-width of random graphs.  Journal of Graph Theory, 70(3):339–347, 2012.
  * [44] Michael Molloy and Bruce Reed.  A critical point for random graphs with a given degree sequence.  Random Structures & Algorithms, 6(2-3):161–180, 1995.
  * [45] Natasha Morrison and Jonathan A Noel.  Extremal bounds for bootstrap percolation in the hypercube.  Journal of Combinatorial Theory, Series A, 156:61–84, 2018.
  * [46] Jaroslav Nešetřil and Patrice Ossona De Mendez.  Sparsity: graphs, structures, and algorithms, volume 28.  Springer Science & Business Media, 2012.
  * [47] Jaroslav Nešetřil, Patrice Ossona de Mendez, and David R Wood.  Characterisations and examples of graph classes with bounded expansion.  European Journal of Combinatorics, 33(3):350–373, 2012.
  * [48] Mark EJ Newman, DJ Walls, Mark Newman, Albert-László Barabási, and Duncan J Watts.  Scaling and percolation in the small-world network model.  In The Structure and Dynamics of Networks, pages 310–320. Princeton University Press, 2011.
  * [49] Mark EJ Newman and Duncan J Watts.  Renormalization group analysis of the small-world network model.  Physics Letters A, 263(4-6):341–346, 1999.
  * [50] Guillem Perarnau and Oriol Serra.  On the tree-depth of random graphs.  Discrete Applied Mathematics, 168:119–126, 2014.
  * [51] Xiao-Long Ren, Niels Gleinig, Dirk Helbing, and Nino Antulov-Fantulin.  Generalized network dismantling.  Proceedings of the national academy of sciences, 116(14):6554–6559, 2019.
  * [52] Eric Riedl.  Largest and smallest minimal percolating sets in trees.  The electronic journal of combinatorics, pages P64–P64, 2012.
  * [53] Neil Robertson and Paul D Seymour.  Graph minors. xiii. the disjoint paths problem.  Journal of combinatorial theory, Series B, 63(1):65–110, 1995.
  * [54] Prathyush Sambaturu, Bijaya Adhikari, B Aditya Prakash, Srinivasan Venkatramanan, and Anil Vullikanti.  Designing effective and practical interventions to contain epidemics.  In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages 1187–1195, 2020.
  * [55] Grant Schoenebeck and Fang-Yi Yu.  Complex contagions on configuration model graphs with a power-law degree distribution.  In International Conference on Web and Internet Economics, pages 459–472. Springer, 2016.

##  Appendix A 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$.

###  A.1 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 19.

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

###### Proof.

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)$:

$\displaystyle A$ $\displaystyle=V$ $\displaystyle B$
$\displaystyle=\\{w_{st}:(s,t)\in E)\\}$ $\displaystyle F$
$\displaystyle=\\{(v,w_{st})\in V\times E:v=s\ \text{or}\ v=t\\}$

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 20.

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.

###### Proof.

The proof of Theorem 19 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}=\\{s,t\\}$ 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 21.

The stopping contagion decision problem is NP-Complete.

###### Proof.

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 19, 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: $\\{z_{2i-1},z_{2i}\\}$ for $1\leq i\leq|A|$. Suppose that
$A=\\{a_{i}:1\leq i\leq|A|\\}.$ 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|\leq\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 22.

The stopping contagion decision problem is NP-Complete when $|A|=2$ and
$|B|=1$.

###### Proof.

We will show the $|A|=2$ and $|B|=1$ cases are hard separately over the
following two lemmas. Taken together, the reductions in Lemma 9 and Lemma 10
naturally compose, which proves our desired result. ∎

Figure 1: $G^{\prime}$ constructed in reduction to the case where $|A|=2$ and
$|B|=1$, Lemma 9 and Lemma 10 respectively (left-to-right). In the diagram
above, three parallel lines represent a complete bipartite linkage between the
two adjacent sets.

######  Lemma 9.

The stopping contagion decision problem is NP-Complete when $|A|=2$.

###### Proof.

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}=\\{s,s^{\prime}\\}$ with
the same optimum. We do this by attaching a large set of vertices
$Z=\\{z_{i}:1\leq i\leq|E|+1\\}$ 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.

$\displaystyle V^{\prime}$ $\displaystyle=V\cup Z\cup A^{\prime}$
$\displaystyle E^{\prime}$ $\displaystyle=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|\geq\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 10.

The stopping contagion decision problem is NP-Complete when $|B|=1$.

###### Proof.

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}=\\{t\\}$.

$\displaystyle V^{\prime}$ $\displaystyle=V\cup S\cup Z\cup B^{\prime}$
$\displaystyle E^{\prime}$ $\displaystyle=E\cup((B\cup S)\times Z)\cup(Z\times
B^{\prime})$

Here, $S=\\{s\\}$ 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}=\\{t\\}$.

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|\geq\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. ∎

###  A.2 Minimizing contagion

######  Theorem 23.

The minimizing contagion decision problem is NP-Complete.

###### Proof.

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 10, we can further
assume $B=\\{b\\}$. 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\leq 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\leq 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. ∎

##  Appendix B 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
[18].

######  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.

  1. 1.

If $X_{r}$ represents the root of $T$, $X_{r}$ and all leaves are empty.

  2. 2.

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

    1. (a)

Introduce Node: A node $X_{i}$ with exactly one child $X_{j}$ such that
$X_{i}=X_{j}\cup\\{u\\}$ for some $u\notin X_{j}$.

    2. (b)

Forget Node: A node $X_{i}$ with exactly one child $X_{j}$ such that
$X_{i}=X_{j}-\\{u\\}$ for some $u\in X_{j}$.

    3. (c)

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 3.

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\\{n,n^{\prime}\\})$ 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 [53]. The second part regarding nice tree
decompositions is from [37]. We are now ready to state our main result.

######  Proposition 4.

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

$\displaystyle O(n^{2}27^{\tau}+\tau n\cdot\ell
81^{\tau}\min\\{r,\Delta\\}^{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$.

###### Proof.

From Proposition 3, 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.

  * •

$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.”

$\displaystyle s:X_{i}\rightarrow\\{\texttt{n},\texttt{s},\texttt{m}\\}$

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)$.

$\displaystyle t^{\prime}:X_{i}\rightarrow\mathbb{N},\
t^{\prime}(u)\in\\{0,\dots,t(u)\\}$

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\leq p\leq\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\leq p\leq\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\leq p\leq\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\\{u\\}$ 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

$\displaystyle(\tilde{t}^{\prime}-S)(v)=\begin{cases}\tilde{t}^{\prime}(v)-1&:v\in
S\\\ \tilde{t}^{\prime}(v)&:v\notin S.\end{cases}$

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:

$\displaystyle B_{i}(p,s,t^{\prime})=\begin{cases}1\\{v\in
B\\}+\min\limits_{\begin{subarray}{c}N\subseteq N_{i}(s)\\\
|N|=t^{\prime}(u)\end{subarray}}B_{j}(p,\tilde{s},\tilde{t}^{\prime}-(N_{i}(s)-N))&:\begin{subarray}{c}s(u)=\texttt{n}\\\
t^{\prime}(u)\leq|N_{i}(s)|\end{subarray}\\\
B_{j}(p,\tilde{s},\tilde{t}^{\prime})&:\begin{subarray}{c}s(u)=\texttt{s}\\\
t^{\prime}(u)>|N_{i}(s)|\end{subarray}\\\
B_{j}(p-1,\tilde{s},\tilde{t}^{\prime})&:s(u)=\texttt{m}\\\
+\infty&:\text{otherwise.}\\\ \end{cases}$

  * •

_Forget Nodes._ Let $X_{i}=X_{j}-\\{u\\}$ be a forget node with child $X_{j}$.
Here, for state mappings $t^{\prime}$ and $s$ on $X_{i}$, denote

$\displaystyle\tilde{t}^{\prime}(v)=\begin{cases}\max\\{0,t(v)-N_{i}(s)\\}&:v=u\\\
t^{\prime}(v)&:v\neq u,\end{cases}$

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.

$\displaystyle B_{j}(p,s,t^{\prime})=\min_{\begin{subarray}{c}\tilde{s}\in
S_{j}\\\ \tilde{s}(v)=s(v)\\\ \forall v\in
X_{i}\end{subarray}}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:

$\displaystyle
B_{i}(p,s,t^{\prime})=\min_{\begin{subarray}{c}p_{j}+p_{k}=p+M(s)\\\
p_{j},p_{k}\geq
M(s)\end{subarray}}\left\\{B_{j}(p_{j},s,t^{\prime})+B_{k}(p_{k},s,t^{\prime})\right\\}.$

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 3 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

$\displaystyle|S_{i}|\leq 3^{n_{i}}\leq 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\\{0,\dots,t(u)\\}$, 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.

$\displaystyle|T_{i}|\leq\min\\{r+1,\Delta+1\\}^{n_{i}}\leq\min\\{r+1,\Delta+1\\}^{(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}\leq(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.

$\displaystyle O(n^{2}27^{\tau}+\tau n\cdot\ell
81^{\tau}\min\\{r,\Delta\\}^{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 5.

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

$\displaystyle O\left((n+m)^{2}27^{\tau}+m\cdot\tau(n+m)\cdot
m81^{\tau}\min\\{r,\max\\{\Delta,2\\}\\}^{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$.

###### Proof.

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

$\displaystyle t(u)=\begin{cases}r&:u\in V-A\\\ 0&:u\in A\\\ 1&:u\in
W,\end{cases}$

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

$\displaystyle|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 4 and including the $m$ pre-factor gives us the
desired runtime.

$\displaystyle O\left((n+m)^{2}27^{\tau}+m\cdot\tau(n+m)\cdot
m81^{\tau}\min\\{r,\max\\{\Delta,2\\}\\}^{4\tau}\cdot(16^{\tau}+m)\right)$

∎

######  Proposition 6.

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

$\displaystyle O\left((n+m)^{2}27^{\tau}+m\cdot\tau(n+m)\cdot
m81^{\tau}\min\\{r,\max\\{\Delta,2\\}\\}^{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$.

###### Proof.

We take a nearly identical approach to that used in Proposition 5. 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

$\displaystyle t(u)=\begin{cases}r&:u\in V-A\\\ 0&:u\in A\\\ 1&:u\in
W,\end{cases}$

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 5.

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 5 yields an identical
runtime, as desired.

$\displaystyle O\left((n+m)^{2}27^{\tau}+m\cdot\tau(n+m)\cdot
m81^{\tau}\min\\{r,\max\\{\Delta,2\\}\\}^{4\tau}\cdot(16^{\tau}+m)\right)$

∎