Ping pong in dangerous graphs: optimal black hole search with pebbles (Q2429323)

This paper studies the black hole search (BHS) problem: a black hole is a vertex where any incoming agent is destroyed without leaving any detectable trace; black hole search is the problem of determining the location of a black hole by a team of identical agents. This problem has been studied in several settings, under a variety of assumptions on the power of the adversary and on the power of the agents. This paper considers the weakest settings that still make the BHS solvable. A first setting is the whiteboard model: every vertex provides a shared space for the arriving agents to read and write. A second setting is the pebble model; it is provided by identical pebbles that can be placed on nodes, picked up and carried by the agents. The main result of this paper is that the pebble model is computationally as powerful as the whiteboard model for BHS in networks of known topology.