Affiliations: Département d'informatique,
Université du Québec en Outaouais, Gatineau,
Québec, J8X 3X7, Canada. E-mail: jurek@uqo.ca | Department of Computer Science, The University of
Liverpool, Chadwick Building, Peach Street, Liverpool L69 7ZF, UK.
E-mail: D.R.Kowalski@csc.liv.ac.uk | Department of Informatics & Telecommunications,
National Kapodistrian University of Athens, Panepistimiopolis 15784 Athens,
Greece. E-mail: emarkou@cs.ntua.gr
Abstract: A black hole is a highly harmful stationary process residing in a
node of a network and destroying all mobile agents visiting the node, without
leaving any trace. We consider the task of locating a black hole in a
(partially) synchronous network, assuming an upper bound on the time of any
edge traversal by an agent. The minimum number of agents capable to identify a
black hole is two. For a given graph and given starting node we are interested
in the fastest possible black hole search by two agents, under the general
scenario in which some subset of nodes is safe and the black hole can be
located in one of the remaining nodes. We show that the problem of finding the
fastest possible black hole search scheme by two agents is NP-hard, and we give
a 9.3-approximation for it.
Keywords: approximation algorithm, black hole, graph, mobile agent, NP-hard problem
