# An efficient curing policy for epidemics on graphs

arXiv: https://arxiv.org/abs/1407.2241 · HTML: https://mlsanity.com/paper/1407.2241/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jul 2014.

## Built on by (most cited first, 2 of 2)

- [Active Screening for Recurrent Diseases: A Reinforcement Learning Approach](https://mlsanity.com/paper/2101.02766/) (2021)
- [Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control](https://mlsanity.com/paper/2506.15397/) (2025)

## Abstract (arXiv)

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.