Network Decontamination with a Single Agent

Abstract

Faults and viruses often spread in networked environments by propagating from site to neighboring site. We model this process of {\em network contamination} by graphs. Consider a graph $G=(V,E)$, whose vertex set is contaminated and our goal is to decontaminate the set $V(G)$ using mobile decontamination agents that traverse along the edge set of $G$. Temporal immunity $\tau (G)\ge 0$ is defined as the time that a decontaminated vertex of $G$ can remain continuously exposed to some contaminated neighbor without getting infected itself. The \emph{immunity number} of $G$, ${\iota }_k(G)$, is the least $\tau$ that is required to decontaminate $G$ using $k$ agents. We study immunity number for some classes of graphs corresponding to network topologies and present upper bounds on ${\iota }_1(G)$, in some cases with matching lower bounds. Variations of this problem have been extensively studied in literature, but proposed algorithms have been restricted to {\em monotone} strategies, where a vertex, once decontaminated, may not be recontaminated. We exploit nonmonotonicity to give bounds which are strictly better than those derived using monotone strategies.