Abstract: We consider the propagation of a contagion process (''epidemic'') on a network, modeled as a controlled SIS process. We study the problem of dynamically allocating a fixed curing budget to the nodes of the graph. The allocation policy is dynamic; it exploits the knowledge of the state of each node as well as the network structure. We show that the expected time until the extinction of the epidemic can be made small (sublinear in the number of nodes) if the curing resources are $\Omega(W)$, where $W$ is the CutWidth of the graph. Conversely, we show that if the curing resources are smaller than a certain constant multiple of the CutWidth, then the expected time to extinction is exponentially large.

Joint work with K. Drakopoulos and A. Ozdaglar.