Network Decontamination with local immunization

We consider the problem of decontaminating a network infected by a mobile virus. The goal is to perform, the task using as small a team of antiviral agents, avoiding any recontamination of disinfected areas, and minimizing the amount of agents' movements across the network. In all the existing literature, it is assumed that the immunity level of a disinfected site is nil. In this paper we consider the network decontamination problem under a new model of immunity to recontamination: we consider the case when a disinfected vertex, after the cleaning agent has gone, will become recontaminated only if a weak majority of its neighbours are infected. We study the effects of this level of immunity on the number of antiviral agents necessary to decontaminate the entire network. We focus on tori and on trees, and establish lower-bounds on the team size; we also establish lower bounds on the number of moves performed by an optimal-size time of cleaners. We design and present strategies for disinfecting tori and trees; we prove that these strategies are optimal in terms of both team size and number of moves. In particular, the upper and lower bounds are are tight for tree networks and for synchronous tori; the bounds are within a constant factor of each other in the case of asynchronous tori.