We provide a dynamic policy for the rapid containment of a contagion process modeled as an SIS epidemic on a bounded degree undirected graph with   $n$       nodes. We show that if the budget   $r$       of curing resources available at each time is   $\Omega (W)$      , where    $W$       is the CutWidth of the graph, and also of order    $\Omega (\log\; n)$      , then the expected time until the extinction of the epidemic is of order   $O(n/r)$      , which is within a constant factor from optimal, as well as sublinear in the number of nodes. Furthermore, if the CutWidth increases only sublinearly with   $n$      , a sublinear expected time to extinction is possible with a sublinearly increasing budget   $r$      .
['Kimon Drakopoulos', 'Asuman E. Ozdaglar', 'John N. Tsitsiklis']
An Efficient Curing Policy for Epidemics on Graphs