Exploring an unknown dangerous graph using tokens

• Published in: Theoretical computer science 2013-02, Vol.472, p.28-45
• Main Authors: Dobrev, Stefan, Flocchini, Paola, Královič, Rastislav, Santoro, Nicola
• Format: Article
• Language: English
• Subjects: Black hole search; Distributed algorithms; Graph exploration; Mobile agent algorithms; Tokens
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2012.11.022

Consider a team of (one or more) mobile agents operating in a graph G. Unaware of the graph topology and starting from the same node, the team must explore the graph. This problem, known as graph exploration, was initially formulated by Shannon in 1951, and has been extensively studied since under a variety of conditions. Most of the existing investigations have assumed that the network is safe for the agents, and the vast majority of the solutions presented in the literature succeed in their task only under this assumption. Recently, the exploration problem has been examined also when the network is unsafe. The danger examined is the presence in the network of a black hole, a node that disposes of any incoming agent without leaving any observable trace of this destruction. The goal is for at least one agent to survive and to have all the surviving agents to construct a map of the network, indicating the edges leading to the black hole. This variant of the problem is also known as a black hole search. This problem has been investigated for the most part assuming powerful inter-agent communication mechanisms: whiteboards at all nodes. Indeed, in this model, the black hole search problem can be solved with an optimal team size and performing a polynomial number of moves. In this paper, we consider the less powerful enhanced token model: each agent has available a token that can be carried, placed on a node or on a link, and can be removed from it. All tokens are identical and no other form of marking or communication is available. We constructively prove that the black hole search problem can be solved also in this model; furthermore, this can be done using a team of agents of optimal size and performing a polynomial number of moves. Our algorithm works even if the agents are asynchronous and if both the agents and the nodes are anonymous.