  The spread of an epidemic is often modeled by an SIR random process on a
social network graph. The MinINF problem for optimal social distancing involves
minimizing the expected number of infections, when we are allowed to break at
most $B$ edges; similarly the MinINFNode problem involves removing at most $B$
vertices. These are fundamental problems in epidemiology and network science.
While a number of heuristics have been considered, the complexity of these
problems remains generally open. In this paper, we present two bicriteria
approximation algorithms for MinINF, which give the first non-trivial
approximations for this problem. The first is based on the cut sparsification
result of Karger \cite{karger:mathor99}, and works when the transmission
probabilities are not too small. The second is a Sample Average Approximation
(SAA) based algorithm, which we analyze for the Chung-Lu random graph model. We
also extend some of our results to tackle the MinINFNode problem.
