Cycling Through a Dangerous Network: A Simple Efficient Strategy for Black Hole Search

In this paper we consider a dangerous process located at a node of a network (called Black Hole ) and a team of mobile agents deployed to locate that node. The nature of the danger is such that when an agent enters the dangerous node, it is trapped there leaving no trace of its destruction. The goal is to deploy as few agents as possible and to locate the black hole in as few moves as possible. We present a simple algorithm that works on any topology (a-priori known by the agents). Our algorithm, based on the pre-computation of an open vertex cover by cycles of the network, uses the optimal number of agents (two); its cost (number of moves) depends on the choice of the cover and it is optimal for several classes of networks.