Premium
Approximation bounds for Black Hole Search problems
Author(s) -
Klasing Ralf,
Markou Euripides,
Radzik Tomasz,
Sarracco Fabiano
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20233
Subject(s) - node (physics) , black hole (networking) , set (abstract data type) , computer science , black box , time complexity , combinatorics , constant (computer programming) , mathematics , process (computing) , theoretical computer science , algorithm , mathematical optimization , computer network , physics , artificial intelligence , routing (electronic design automation) , routing protocol , quantum mechanics , programming language , link state routing protocol , operating system
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. The Black Hole Search is the task of locating all black holes in a network, through the exploration of its nodes by a set of mobile agents. In this article we consider the problem of designing the fastest Black Hole Search, given the map of the network, the starting node and a subset of nodes of the network initially known to be safe. We study the version of this problem that assumes that there is at most one black hole in the network and there are two agents, which move in synchronized steps. We prove that this problem is not polynomial‐time approximable within any constant factor less than $389 \over 388$ (unless P = NP ). We give a 6‐approximation algorithm, thus improving on the 9.3‐approximation algorithm from (Czyzowicz et al., Fundamenta Informaticae 71 (2006), 229–242). We also prove APX‐hardness for a restricted version of the problem, in which only the starting node is initially known to be safe. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008