  We consider the propagation of a contagion process (epidemic) on a network
and study the problem of dynamically allocating a fixed curing budget to the
nodes of the graph, at each time instant. For bounded degree graphs, we provide
a lower bound on the expected time to extinction under any such dynamic
allocation policy, in terms of a combinatorial quantity that we call the
resistance of the set of initially infected nodes, the available budget, and
the number of nodes n. Specifically, we consider the case of bounded degree
graphs, with the resistance growing linearly in n. We show that if the curing
budget is less than a certain multiple of the resistance, then the expected
time to extinction grows exponentially with n. As a corollary, if all nodes are
initially infected and the CutWidth of the graph grows linearly, while the
curing budget is less than a certain multiple of the CutWidth, then the
expected time to extinction grows exponentially in n. The combination of the
latter with our prior work establishes a fairly sharp phase transition on the
expected time to extinction (sub-linear versus exponential) based on the
relation between the CutWidth and the curing budget.
