Network Decontamination with a Single Agent

Faults and viruses often spread in networked environments by propagating from site to neighboring sites. We model this process of network contamination by graphs. Consider a graph \(G=(V,E)\), whose vertex set is contaminated and our goal is to decontaminate the set \(V\) 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 immunity number of \(G\), \(\iota _k(G)\), is the least \(\tau (G)\) 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 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.