DIMACS TR: 2007-06

On complexity of algorithms for modeling disease transmission

Authors: Endre Boros and Vladimir Gurvich


We consider simple deterministic models of disease transmission. Given a set of individuals $I$, we assign a hypergraph $H_i = (I \setminus \{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$ respectively. We 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$ or $M_D$ and targets $T_I,T_q$ or $T_H$. We also consider enumeration problems and show that if the transmission rule is given explicitly, $M_R$, then all inclusion minimal sources can be generated in incremental polynomial time for all targets $T_I,T_q$, or $T_H$. On the other hand, generating minimal sources is hard for all targets if the transmission model is given by a (directed) graph, $M_G$ or $M_D$, since for these two cases the input size may be logarithmic in the input size of $M_R$. Indeed, given $G = (I,E)$ and $k(i)$ for all $i \in I$, a corresponding hypergraph $H_i$ for some $i \in I$ may be exponential in $|I|$ unless $k(i)$ is bounded by a constant.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2007/2007-06.pdf
DIMACS Home Page