Tree exploration with logarithmic memory

Abstract

We consider the task of network exploration by a mobile agent (robot) with small memory. The agent has to traverse all nodes and edges of a network (represented as an undirected connected graph), and return to the starting node. Nodes of the network are unlabeled and edge ports are locally labeled at each node. The agent has no a priori knowledge of the topology of the network or of its size, and cannot mark nodes in any way. Under such weak assumptions, cycles in the network may prevent feasibility of exploration, hence we restrict attention to trees. We present an algorithm to accomplish tree exploration (with return) using O(log n)-bit memory for all n-node trees. This strengthens the result from Diks et al. [2004], where O(log ² n)-bit memory was used for tree exploration, and matches the lower bound on memory size proved there. We also extend our O(log n)-bit memory traversal mechanism to a weaker model in which ports at each node are ordered in circular manner, however, the explicit values of port numbers are not available.

References

1. Albers, S. 1999. Better bounds for online scheduling. SIAM J. Comput. 29, 2, 459--473.
2. Aleliunas, R., Karp, R. M., Lipton, R. J., Lovász, L., and Rackoff, C. 1979. Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science (FOCS'79). IEEE Computer Society, Los Alamitos, CA, 218--223.
3. Alon, N., Azar, Y., and Ravid, Y. 1990. Universal sequences for complete graphs. Discr. Appl. Math. 27, 1-2, 25--28.
4. Awerbuch, B., Betke, M., Rivest, R. L., and Singh, M. 1995. Piecemeal graph exploration by a mobile robot (extended abstract). In Proceedings of the 8th Annual Conference on Computational Learning Theory (COLT'95). ACM, New York, 321--328.
5. Babai, L., Nisan, N., and Szegedy, M. 1989. Multiparty protocols and logspace-hard pseudorandom sequences (extended abstract). In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC'89). ACM, New York, 1--11.
6. Bar-Noy, A., Borodin, A., Karchmer, M., Linial, N., and Werman, M. 1989. Bounds on universal sequences. SIAM J. Comput. 18, 2, 268--277.
7. Bender, M. A., Fernández, A., Ron, D., Sahai, A., and Vadhan, S. P. 1998. The power of a pebble: Exploring and mapping directed graphs. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC'98). ACM, New York, 269--278.
8. Bender, M. A. and Slonim, D. K. 1994. The power of team exploration: Two robots can learn unlabeled directed graphs. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS'94). IEEE Computer Society, Los Alamitos, CA, 75--85.
9. Betke, M., Rivest, R. L., and Singh, M. 1995. Piecemeal learning of an unknown environment. Mach. Learn. 18, 2-3, 231--254.
10. Bridgland, M. F. 1987. Universal traversal sequences for paths and cycles. J. Algor. 8, 3, 395--404.
11. Buss, J. F. and Tompa, M. 1995. Lower bounds on universal traversal sequences based on chains of length five. Inf. Comput. 120, 2, 326--329.
12. Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., and Peleg, D. 2008. Label-Guided graph exploration by a finite automaton. ACM Trans. Algor. 4, 4, 1--18.
13. Deng, X. and Papadimitriou, C. H. 1999. Exploring an unknown graph. J. Graph Theory 32, 265--297.
14. Diks, K., Fraigniaud, P., Kranakis, E., and Pelc, A. 2004. Tree exploration with little memory. J. Algor. 51, 1, 38--63.
15. Duncan, C. A., Kobourov, S. G., and Kumar, V. S. A. 2006. Optimal constrained graph exploration. ACM Trans. Algor. 2, 3, 380--402.
16. Fraigniaud, P. and Ilcinkas, D. 2004. Digraphs exploration with little memory. In Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS'04). Lecture Notes in Computer Science, vol. 2996. Springer, 246--257.
17. Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., and Peleg, D. 2005a. Graph exploration by a finite automaton. Theor. Comput. Sci. 345, 2-3, 331--344.
18. Fraigniaud, P., Ilcinkas, D., Rajsbaum, S., and Tixeuil, S. 2005b. Space lower bounds for graph exploration via reduced automata. In Proceedings of the 12th International Colloquium on Structural Information and Communication Complexity (SIROCCO'05). Lecture Notes in Computer Science, vol. 3499. Springer, 140--154.
19. Hoory, S. and Wigderson, A. 1993. Universal traversal sequences for expander graphs. Inf. Process. Lett. 46, 2, 67--69.
20. Impagliazzo, R., Nisan, N., and Wigderson, A. 1994. Pseudorandomness for network algorithms. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC'94). ACM, New York, 356--364.
21. Istrail, S. 1988. Polynomial universal traversing sequences for cycles are constructible (extended abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC'88). ACM, New York, 491--503.
22. Karloff, H. J., Paturi, R., and Simon, J. 1988. Universal traversal sequences of length n^o(log n) for cliques. Inf. Process. Lett. 28, 5, 241--243.
23. Koucký, M. 2002. Universal traversal sequences with backtracking. J. Comput. Syst. Sci. 65, 4, 717--726.
24. Koucký, M. 2003. Log-Space constructible universal traversal sequences for cycles of length o(n^4.03). Theor. Comput. Sci. 296, 1, 117--144.
25. Nisan, N. 1992. Pseudorandom generators for space-bounded computation. Combinatorica 12, 4, 449--461.
26. Panaite, P. and Pelc, A. 1999. Exploring unknown undirected graphs. J. Algor. 33, 2, 281--295.
27. Reingold, O. 2008. Undirected connectivity in log-space. J. ACM 55, 4, 1--24.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Combinatorial algorithms

    • Graph theory

      • Graph enumeration

      • Network flows

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

      • Pattern matching

    • Graph algorithms analysis

      • Network flows

  • Randomness, geometry and discrete structures