Abstract
We consider the problem of cooperative network exploration by agents under the assumption that there is a harmful host present in the network that destroys the incoming agents without outside trace – the so-called black hole search problem.
Many variants of this problem have been studied, with various assumptions about the timing, agents’ knowledge about the topology, means of inter-agent communication, amount of writable memory in vertices, and other parameters. However, all this research considered undirected graphs only, and relied to some extent on the ability of an agent to mark an edge as safe immediately after having traversed it.
In this paper we study directed graphs where this technique does not apply, and show that the consequence is an exponential gap: While in undirected graphs Δ + 1 agents are always sufficient, in the directed case at least 2Δ agents are needed in the worst case, where Δ is in-degree of the black hole. This lower bound holds also in the case of synchronous agents. Furthermore, we ask the question What structural information is sufficient to close this gap? and show that in planar graphs with a planar embedding known to the agents, 2Δ + 1 agents are sufficient, and 2Δ agents are necessary.
Research supported by grant APVV-0433-06.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. Kluwer, Dordrecht (2003)
Arkin, E., Bender, M., Fekete, S., Mitchell, J.: The freeze-tag problem: how to wake up a swarm of robots. In: 13th ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pp. 568–577 (2002)
Barriere, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Capture of an intruder by mobile agents. In: Proc. 14th ACM Symp. on Parallel Algorithms and Architectures (SPAA 2002), pp. 200–209 (2002)
Bender, M.A., Slonim, D.: The power of team exploration: Two robots can learn unlabeled directed graphs. In: 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), pp. 75–85 (1994)
Bender, M., Slonim, D.K.: The power of team exploration: two robots can learn unlabeled directed graphs. In: Proc. 35th Symp. on Foundations of Computer Science (FOCS 1994), pp. 75–85 (1994)
Bender, M.A., Fernández, A., Ron, D., Sahai, A., Vadhan, S.P.: The power of a pebble: Exploring and mapping directed graphs. In: STOC, pp. 269–278 (1998)
Budach, L.: On the solution of the labyrinth problem for finite automata. Elektronische Informationsverarbeitung und Kybernetic 11, 661–672 (1975)
Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. ACM Transactions on Algorithms 4(4) (2008)
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)
Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. In: Proceedings: 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, October 22–24, vol. 1, pp. 355–361 (1990); Formerly called the Annual Symposium on Switching and Automata Theory. IEEE catalog number 90CH29256. Computer Society order no. 2082
Dobrev, S., Flocchini, P., Kralovic, R., Prencipe, G., Ruzicka, P., Santoro, N.: Optimal search for a black hole in common interconnection networks. Networks 47(2), 61–71 (2006)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Finding a black hole in an arbitrary network: optimal mobile agents protocols. In: Proc. of 21st ACM Symposium on Principles of Distributed Computing (PODC 2002), pp. 153–162 (2002)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Finding a black hole in an arbitrary network: optimal mobile agents protocols. In: Proc. of 21st ACM Symposium on Principles of Distributed Computing (PODC 2002), pp. 153–162 (2002)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Multiple agents rendezvous in a ring in spite of a black hole. In: Papatriantafilou, M., Hunel, P. (eds.) OPODIS 2003. LNCS, vol. 3144, pp. 34–46. Springer, Heidelberg (2004)
Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Mobile search for a black hole in an anonymous ring. Algorithmica 48(1), 67–90 (2007)
Dobrev, S., Flocchini, P., Santoro, N.: Improved bounds for optimal black hole search in a network with a map. In: Kralovic, R., Sýkora, O. (eds.) SIROCCO 2004. LNCS, vol. 3104, pp. 111–122. Springer, Heidelberg (2004)
Esparza, O., Soriano, M., Munoz, J., Forne, J.: Host revocation authority: A way of protecting mobile agents from malicious hosts. In: Cueva Lovelle, J.M., Rodríguez, B.M.G., Gayo, J.E.L., Ruiz, M.d.P.P., Aguilar, L.J. (eds.) ICWE 2003. LNCS, vol. 2722. Springer, Heidelberg (2003)
Fraigniaud, P., Gasieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks 48(3), 166–177 (2006)
Fraigniaud, P., Ilcinkas, D.: Digraph exploration with little memory. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 246–257. Springer, Heidelberg (2004)
Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theor. Comput. Sci. 345(2-3), 331–344 (2005)
Fraigniaud, P., Ilcinkas, D., Pelc, A.: Impact of memory size on graph exploration capability. Discrete Applied Mathematics 156(12), 2310–2319 (2008)
Fraigniaud, P., Ilcinkas, D., Pelc, A.: Tree exploration with advice. Inf. Comput. 206(11), 1276–1287 (2008)
Gasieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. In: Bansal, N., Pruhs, K., Stein, C. (eds.) SODA, pp. 585–594. SIAM, Philadelphia (2007)
Greenberg, M., Byington, J., Harper, D.G.: Mobile agents and security. IEEE Commun. Mag. 36(7), 76–85 (1998)
Hoffmann, F.: One pebble does not suffice to search plane labyrinths. In: Gecseg, F. (ed.) FCT 1981. LNCS, vol. 117, pp. 433–444. Springer, Heidelberg (1981)
Jennings, N.R.: On agent-based software engineering. Artificial Intelligence 117(2), 277–296 (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)
Marco, G.D., Gargano, L., Kranakis, E., Krizanc, D., Pelc, A., Vaccaro, U.: Asynchronous deterministic rendezvous in graphs. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 271–282. Springer, Heidelberg (2005)
Oppliger, R.: Security issues related to mobile code and agent-based systems. Computer Communications 22(12), 1165–1170 (1999)
Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33, 281–295 (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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Czyzowicz, J., Dobrev, S., Královič, R., Miklík, S., Pardubská, D. (2010). Black Hole Search in Directed Graphs. In: Kutten, S., Žerovnik, J. (eds) Structural Information and Communication Complexity. SIROCCO 2009. Lecture Notes in Computer Science, vol 5869. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11476-2_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-11476-2_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11475-5
Online ISBN: 978-3-642-11476-2
eBook Packages: Computer ScienceComputer Science (R0)