Exploring and making safe dangerous networks using mobile entities

We consider synchronous and mobile entities that have to explore and make safe a network with faulty nodes, called black-holes, that destroy any entering entity. We are interested in the scenario where the destruction of an entity by means of a black-hole also affects all the entities within a fixed range r (in terms of hops), and we ask for the minimum number of synchronized steps needed to remove all the black-holes from that network. Clearly, if there are b black-holes in the network, then k ≥ b entities are necessary. First, we show that the problem is NP-hard even for b = k = 1; second, we provide an asymptotical optimal solution for the case of r = 0 and a general lower bound for the case of r > 0; third, we propose two different strategies plus a refined heuristic for the case of r = 1, and we prove they are all asymptotically optimal; finally, we provide an experimental study to show the practical performance of the proposed strategies.