Title: On Complexity of Algorithms for Modeling Disease Transmission and Vaccination Strategies
Speaker: Vladimir Gurvich, Rutgers University
Date: April 9, 2007 12:00 - 1:30 pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We consider simple deterministic models of disease transmission. Given a set of individuals $I$, we assign a hypergraph $H_i = (I \set minus \{ i \}, E_i)$ to each $ i \in I $ and assume that $i$ will be infected whenever there is a fully infected edge $e \in E_i$.
Along with this general model $M_H$ we also study two special cases $M_G$ and $M_D$ when for all $ i \in I $ the hypergraphs $H_i$ are specified implicitly by a (directed) graph $G = (I,E)$ and integral positive thresholds $k(i)$ for all $ i \in I $. Then we assume that $i$ will be infected whenever at least $k(i)$ of his neighbors (predecessors) are infected.
Given a set $S$ of the originally infected individuals (a source) we generate the closure $T(S) = cl(S)$, that is, the set of all individuals that will be infected if the above transmission rules are applied iteratively sufficiently many times. We study all minimal sources such that (i) $T(S) = I$, or (ii) $T(S)$ contains a given individual $q \in I$, or (iii) $T(S)$ contains an edge of a given ``target'' hypergraph $H$.
We denote these three types of ``targets'' by $T_I, T_q$, and $T_H$ and show that, given a threshold $t$, it is NP-complete to decide whether there is a source $S$ of size at most $t$. The problem remains NP-complete for each of the three models $M_R, M_G, M_D$ and targets $T_I, T_q, T_H$ defined above.
We also consider the corresponding ENUMERATION problems and show that, in contrast to the "optimization" versions, some of them are tractable. In particular, if the transmission rule is given explicitly, $M_R$, then all inclusion minimal sources can be generated in incremental polynomial time for targets $T_I, T_q$, and $T_H$. The problem is reduced to enumerating all minimal implicants of a Horn DNF for which an efficient algorithm was recently obtained by T. Eiter and K. Makino.
On the other hand, generating minimal sources is NP-hard for all three types of targets if the transmission model is given by a (directed) graph, $M_G$ or $M_D$, although each of these two models is a special cases of $M_R$. This "paradox" can be easily explained as follows. The input size of $M_G$ and $M_D$ may be logarithmic in the input size of $M_R$. Indeed, given $G = (I,E)$ and $k(i)$ for all $i \in I$, the corresponding hypergraph $H_i$ for some $i \in I$ may be exponential in $ | I | $ unless $k(i)$ is bounded by a constant.
Joint work with Endre Boros.
see: DIMACS Computational and Mathematical Epidemiology Seminar Series 2006 - 2007