An Efficient Curing Policy for Epidemics on Graphs

We provide a dynamic policy for the rapid containment of a contagion process modeled as an SIS epidemic on a bounded degree undirected graph withnnodes. We show that if the budgetrof curing resources available at each time isΩ (W), whereWis the CutWidth of the graph, and also of orderΩ (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 withn, a sublinear expected time to extinction is possible with a sublinearly increasing budgetr.