Skip to Main content Skip to Navigation
Reports

Hardness and Approximation Results for Black Hole Search in Arbitrary Networks

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 and the starting node. 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 NP-hard in arbitrary graphs (even in planar graphs) thus solving an open problem stated in . We also give a -approximation algorithm, showing the first non-trivial approximation ratio upper bound for this problem. Our algorithm follows a natural approach of exploring the network via a spanning tree. We prove that this approach cannot lead to an approximation ratio bound better than 3/2.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00070349
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 8:13:40 PM
Last modification on : Thursday, November 26, 2020 - 4:00:02 PM
Long-term archiving on: : Sunday, April 4, 2010 - 9:00:52 PM

Identifiers

  • HAL Id : inria-00070349, version 1

Collections

Citation

Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Saracco. Hardness and Approximation Results for Black Hole Search in Arbitrary Networks. [Research Report] RR-5659, INRIA. 2006, pp.36. ⟨inria-00070349⟩

Share

Metrics

Record views

338

Files downloads

274