DIMACS TR: 2007-06
On complexity of algorithms for modeling disease transmission
Authors: Endre Boros and Vladimir Gurvich
ABSTRACT
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