Abstract
We consider the task of exploring graphs with anonymous nodes by a team of non-cooperative robots, modeled as finite automata. For exploration to be completed, each edge of the graph has to be traversed by at least one robot. In this paper, the robots have no a priori knowledge of the topology of the graph, nor of its size, and we are interested in the amount of memory the robots need to accomplish exploration, We introduce the so-called reduced automata technique, and we show how to use this technique for deriving several space lower bounds for exploration. Informally speaking, the reduced automata technique consists in reducing a robot to a simpler form that preserves its “core” behavior on some graphs. Using this technique, we first show that any set of q≥ 1 non-cooperative robots, requires \(\Omega(\log(\frac{n}{q}))\) memory bits to explore all n-node graphs. The proof implies that, for any set of qK-state robots, there exists a graph of size O(qK) that no robot of this set can explore, which improves the O(K O(q)) bound by Rollik (1980). Our main result is an application of this latter result, concerning terminating graph exploration with one robot, i.e., in which the robot is requested to stop after completing exploration. For this task, the robot is provided with a pebble, that it can use to mark nodes (without such a marker, even terminating exploration of cycles cannot be achieved). We prove that terminating exploration requires Ω(log n) bits of memory for a robot achieving this task in all n-node graphs.
A preliminary version of this paper appears in the proceedings of the 12th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Mont Saint-Michel, France, May 24-26, 2005, as part of [13].
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aleliunas, R., Karp, R., Lipton, R., Lovasz, L., Rackoff, C.: Random walks, universal traversal sequences, and the time complexity of maze problems. In: Proc. of the 20th Annual Symposium on Foundations of Computer Science (FOCS), pp. 218–223 (1979)
Bhatt, S.N., Even, S., Greenberg, D.S., Tayar, R.: Traversing Directed Eulerian Mazes. J. Graph Algorithms Appl. 6(2), 157–173 (2002)
Bender, M., Fernandez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: Exploring and mapping directed graphs. Information and Computation 176, 1–21 (2002) (Prel. Version in STOC 1998)
Bender, M., Slonim, D.: The power of team exploration: Two robots can learn unlabeled directed graphs. In: 35th Ann. Symp. on Foundations of Computer Science (FOCS), pp. 75–85 (1994)
Budach, L.: Automata and labyrinths. Math. Nachrichten, 195–282 (1978)
Cook, S., Rackoff, C.: Space lower bounds for maze threadability on restricted machines. SIAM J. on Computing 9(3), 636–652 (1980)
Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree Exploration with Little Memory. In: 13th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 588–597 (2002) (Full version to appear in J. of Algorithms)
Dudek, G., Jenkins, M., Milios, E., Wilkes, D.: Robotic Exploration as Graph Construction. IEEE Transaction on Robotics and Automation 7(6), 859–865 (1991)
Even, S., Itkis, G., Rajsbaum, S.: On Mixed Connectivity Certificates. Theor. Comput. Sci. 203(2), 253–269 (1998)
Even, S., Litman, A., Winkler, P.: Computing with Snakes in Directed Networks of Automata. J. Algorithms 24(1), 158–170 (1997)
Even, S., Tarjan, R.E.: Computing an st -Numbering. Theor. Comput. Sci. 2(3), 339–344 (1976)
Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph Exploration by a Finite Automaton. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 451–462. Springer, Heidelberg (2004) (Full version to appear in Theoretical Computer Science)
Fraigniaud, P., Ilcinkas, D., Rajsbaum, S., Tixeuil, S.: Space lower bounds for graph exploration via reduced automata. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol. 3499, pp. 140–154. Springer, Heidelberg (2005)
Kouckỳ, M.: Universal Traversal Sequences with Backtracking. In: Proc. 16th IEEE Conference on Computational Complexity, pp. 21–26 (2001) (Also, to appear in J. Computer and System Sciences)
Reingold, O.: Undirected ST-Connectivity in Log-Space. To appear in 37th ACM Symp. on Theory of Computing, STOC (2005)
Rollik, H.-A.: Automaten in planaren graphen. Acta Informatica 13, 287–298 (1980)
Shannon, C.-E.: Presentation of a Maze-Solving Machine. In: 8th Conf. of the Josiah Macy Jr. Found (Cybernetics), pp. 173–180 (1951)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Fraigniaud, P., Ilcinkas, D., Rajsbaum, S., Tixeuil, S. (2006). The Reduced Automata Technique for Graph Exploration Space Lower Bounds. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds) Theoretical Computer Science. Lecture Notes in Computer Science, vol 3895. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11685654_1
Download citation
DOI: https://doi.org/10.1007/11685654_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32880-3
Online ISBN: 978-3-540-32881-0
eBook Packages: Computer ScienceComputer Science (R0)