Social Models and Algorithms for Optimization of Contact Immunity of Oral Polio Vaccine

摘要

Oral polio vaccine (OPV) can produce contact immunity and help protect more individuals than the vaccinated from polio. To better capture the utilization of OPV's contact immunity, we model the community as a social network, and formulate the task of maximizing the contact immunity effect as an optimization problem on graphs, which is to find a sequence of vertices to be "vaccinated" to maximize the total number of "infected" vertices. Furthermore, we consider the restriction imported by immune deficient individuals, and study related problems. We present polynomial-time algorithms for these problems on trees, and show the intractability of problems on general graphs.