  This paper studies efficient algorithms for dynamic curing policies and the
corresponding network design problems to guarantee the fast extinction of
epidemic spread in a susceptible-infected-susceptible (SIS) model. We consider
a Markov process-based SIS epidemic model. We call a curing policy fair if
demographic groups are cured with comparable speeds. We propose a fair curing
policy based on the curing policy of Drakopoulos et al. Since these
optimization problems are NP-hard, finding optimal policies is intractable for
large graphs. We provide approximation guarantees on both curing and fair
curing policies. Moreover, when the total infection rate is large, the original
curing policy includes a waiting period in which no measures are taken to
mitigate the spread until the rate slows down. To avoid the waiting period, we
study network design problems to reduce the total infection rate by deleting
edges or reducing the weight of edges. Then the curing processes become
continuous since the total infection rate is restricted by network design. We
provide algorithms with provable guarantees for the considered network design
problems. In summary, the proposed fair curing and network design algorithms
together provide an effective, fair, and computationally efficient approach
that mitigates SIS epidemic spread in networks.
