Abstract
We consider collaborative graph exploration with a set of k agents. All agents start at a common vertex of an initially unknown graph with n vertices and need to collectively visit all other vertices. We assume agents are deterministic, moves are simultaneous, and we allow agents to communicate globally. For this setting, we give the first non-trivial lower bounds that bridge the gap between small (\(k \le \sqrt{n}\)) and large (\(k \ge n\)) teams of agents. Remarkably, our bounds tightly connect to existing results in both domains.
First, we significantly extend a lower bound of \(\varOmega (\log k / \log \log k)\) by Dynia et al. on the competitive ratio of a collaborative tree exploration strategy to the range \(k \le n \log ^c n\) for any \(c \in \mathbb {N}\). Second, we provide a tight lower bound on the number of agents needed for any competitive exploration algorithm. In particular, we show that any collaborative tree exploration algorithm with \(k=Dn^{1+o(1)}\) agents has a competitive ratio of \(\omega (1)\), while Dereniowski et al. gave an algorithm with \(k=Dn^{1+\varepsilon }\) agents and competitive ratio \(\mathcal {O}(1)\), for any \(\varepsilon > 0\) and with D denoting the diameter of the graph. Lastly, we show that, for any exploration algorithm using \(k=n\) agents, there exist trees of arbitrarily large height D that require \(\varOmega (D^2)\) rounds, and we provide a simple algorithm that matches this bound for all trees.
Y. Disser—Supported by the ‘Excellence Initiative’ of the German Federal and State Governments and the Graduate School CE at TU Darmstadt.
F. Mousset—Supported by grant no. 6910960 of the Fonds National de la Recherche, Luxembourg.
A. Noever—Supported by grant no. 200021 143338 of the Swiss National Science Foundation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164–1188 (2000)
Aleliunas, R., Karp, R.M., Lipton, R.J., Lovász, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: Proceedings of the 20th Annual Symposium on Foundations of Computer Science (FOCS), pp. 218–223 (1979)
Alon, N., Avin, C., Koucký, M., Kozma, G., Lotker, Z., Tuttle, M.R.: Many random walks are faster than one. Comb. Probab. Comput. 20(4), 481–502 (2011)
Ambühl, C., Gąsieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. ACM Trans. Algorithms 7(2), 1–21 (2011)
Awerbuch, B., Betke, M., Rivest, R.L., Singh, M.: Piecemeal graph exploration by a mobile robot. Inf. Comput. 152(2), 155–172 (1999)
Bender, M.A., Fernández, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: exploring and mapping directed graphs. Inf. Comput. 176(1), 1–21 (2002)
Bender, M.A., Slonim, D.K.: The power of team exploration: two robots can learn unlabeled directed graphs. In: Proceedings of 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 75–85 (1994)
Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS), pp. 132–142 (1978)
Chalopin, J., Das, S., Disser, Y., Mihalák, M., Widmayer, P.: Mapping simple polygons: how robots benefit from looking back. Algorithmica 65(1), 43–59 (2011)
Chalopin, J., Das, S., Disser, Y., Mihalák, M., Widmayer, P.: Mapping simple polygons. ACM Trans. Algorithms 11(4), 1–16 (2015)
Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. Graph Theory 32(3), 265–297 (1999)
Dereniowski, D., Disser, Y., Kosowski, A., Pająk, D., Uznański, P.: Fast collaborative graph exploration. Inf. Comput. 243, 37–49 (2015)
Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. J. Algorithms 51(1), 38–63 (2004)
Disser, Y., Hackfeld, J., Klimm, M.: Undirected graph exploration with \(\varTheta (\log \log n)\) pebbles. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 25–39 (2016)
Duncan, C.A., Kobourov, S.G., Kumar, V.S.A.: Optimal constrained graph exploration. ACM Trans. Algorithms 2, 380–402 (2006)
Dynia, M., Łopuszański, J., Schindelhauer, C.: Why robots need maps. In: Prencipe, G., Zaks, S. (eds.) SIROCCO 2007. LNCS, vol. 4474, pp. 41–50. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72951-8_5
Elsässer, R., Sauerwald, T.: Tight bounds for the cover time of multiple random walks. Theor. Comput. Sci. 412(24), 2623–2641 (2011)
Fraigniaud, P., Gąsieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks 48(3), 166–177 (2006)
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)
Higashikawa, Y., Katoh, N., Langerman, S., Tanigawa, S.I.: Online graph exploration algorithms for cycles and trees by multiple searchers. J. Comb. Optim. 28(2), 480–495 (2012)
Hoffmann, F.: One pebble does not suffice to search plane labyrinths. In: Proceedings of the 3rd International Symposium on Fundamentals of Computation Theory (FCT), pp. 433–444 (1981)
Ortolf, C., Schindelhauer, C.: Online multi-robot exploration of grid graphs with rectangular obstacles. In: Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 27–36 (2012)
Ortolf, C., Schindelhauer, C.: A recursive approach to multi-robot exploration of trees. In: Halldórsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 343–354. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-09620-9_26
Ortolf, C., Schindelhauer, C.: Strategies for parallel unaware cleaners. Theor. Comput. Sci. 608, 178–189 (2015)
Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 1–24 (2008)
Acknowledgments
We would like to thank Rajko Nenadov for useful discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Disser, Y., Mousset, F., Noever, A., Škorić, N., Steger, A. (2017). A General Lower Bound for Collaborative Tree Exploration. In: Das, S., Tixeuil, S. (eds) Structural Information and Communication Complexity. SIROCCO 2017. Lecture Notes in Computer Science(), vol 10641. Springer, Cham. https://doi.org/10.1007/978-3-319-72050-0_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-72050-0_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-72049-4
Online ISBN: 978-3-319-72050-0
eBook Packages: Computer ScienceComputer Science (R0)