Network decontamination under mm-immunity

We consider the problem of decontaminating an infected network using as few mobile cleaning agents as possible and avoiding recontamination. After a cleaning agent has left a vertex vv, this vertex will become recontaminated if mm or more of its neighbors are infected, where m≥1m≥1 is a threshold parameter of the system indicating the local immunity level of the network. This network decontamination problem, also called monotone connected graph search and intruder capture  , has been extensively studied in the literature when m=1m=1 (no immunity).In this paper, we extend these investigations and consider for the first time the network decontamination problem when the parameter mm is an arbitrary integer value m≥1m≥1. We direct our study to widely used interconnection networks, namely meshes, tori, and trees. For each of these classes of networks, we present decontamination algorithms with threshold mm; these algorithms work even in asynchronous setting, either directly or with a simple modification requiring one additional agent. We also establish general lower bounds on the number of agents necessary for decontamination with immunity mm; these bounds are tight in the case of trees, while large gaps still exist in the case of meshes and tori.