  This paper studies algorithmic strategies to effectively reduce the number of
infections in susceptible-infected-recovered (SIR) epidemic models. We consider
a Markov chain SIR model and its two instantiations in the deterministic SIR
(D-SIR) model and the independent cascade SIR (IC-SIR) model. We investigate
the problem of minimizing the number of infections by restricting contacts
under realistic constraints. Under moderate assumptions on the reproduction
number, we prove that the infection numbers are bounded by supermodular
functions in the D-SIR model and the IC-SIR model for large classes of random
networks. We propose efficient algorithms with approximation guarantees to
minimize infections. The theoretical results are illustrated by numerical
simulations.
