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. 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 paper we consider the problem of designing the fastest Black Hole Search, given the map of the network, the starting node and, possibly, 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 \(\frac{389}{388}\) (unless P=NP). We give a 6-approximation algorithm, thus improving on the 9.3-approximation algorithm from [3]. We also prove APX-hardness for a restricted version of the problem, in which only the starting node is initially known to be safe.
Research supported in part by the European projects IST FET AEOLUS and COST Action TIST 293 (GRAAL), the Royal Society Grant ESEP 16244, and the ACI Masses de données. Part of this work was done while T. Radzik and F. Sarracco were visiting the LaBRI (Laboratoire Bordelais de Recherche en Informatique) in Bordeaux.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Csaba, B., Karpinski, M., Krysta, P.: Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. In: SODA 2002: Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 74–83 (2002)
Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A.: Searching for a black hole in tree networks. In: Higashino, T. (ed.) OPODIS 2004. LNCS, vol. 3544, pp. 67–80. Springer, Heidelberg (2005)
Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A.: Complexity of searching for a black hole. Fundamenta Informaticae (to appear, 2006)
Dobrev, S., Flocchini, P., Kralovic, R., Prencipe, G., Ruzicka, P., Santoro, N.: Black hole search by mobile agents in hypercubes and related networks. In: Proc. 6th Int. Conf. on Principles of Distributed Systems (OPODIS 2002), pp. 169–180 (2002)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Mobile agents searching for a black hole in an anonymous ring. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol. 2180, pp. 166–179. Springer, Heidelberg (2001)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Searching for a black hole in arbitrary networks: Optimal mobile agents protocols. In: Proc. 21st ACM Symposium on Principles of Distributed Computing (PODC 2002), pp. 153–161 (2002)
Engebretsen, L., Karpinski, M.: TSP with bounded metrics: stronger approximation hardness. Technical Report 85264, University of Bonn (February 2005)
Hohl, F.: Time limited black box security: Protecting mobile agents from malicious hosts. In: Vigna, G. (ed.) Mobile Agents and Security. LNCS, vol. 1419, pp. 92–113. Springer, Heidelberg (1998)
Hohl, F.: A framework to protect mobile agents by using reference states. In: Proc. 20th Int. Conf. on Distributed Computing Systems (ICDCS 2000), pp. 410–417 (2000)
Klasing, R., Markou, E., Radzik, T., Sarracco, F.: Hardness and approximation results for black hole search in arbitrary graphs. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol. 3499, pp. 200–215. Springer, Heidelberg (2005)
Ng, S., Cheung, K.: Protecting mobile agents against malicious hosts by intention of spreading. In: Arabnia, H. (ed.) Proc. Int. Conf. on Parallel and Distributed Processing and Applications (PDPTA 1999), vol. II, pp. 725–729 (1999)
Sander, T., Tschudin, C.F.: Protecting mobile agents against malicious hosts. In: Vigna, G. (ed.) Mobile Agents and Security. LNCS, vol. 1419, pp. 44–60. Springer, Heidelberg (1998)
Schelderup, K., Olnes, J.: Mobile agent security – issues and directions. In: Zuidweg, H., Campolargo, M., Delgado, J., Mullery, A. (eds.) IS&N 1999. LNCS, vol. 1597, pp. 155–167. Springer, Heidelberg (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Klasing, R., Markou, E., Radzik, T., Sarracco, F. (2006). Approximation Bounds for Black Hole Search Problems. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds) Principles of Distributed Systems. OPODIS 2005. Lecture Notes in Computer Science, vol 3974. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11795490_21
Download citation
DOI: https://doi.org/10.1007/11795490_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36321-7
Online ISBN: 978-3-540-36322-4
eBook Packages: Computer ScienceComputer Science (R0)