# The Reduced Automata Technique for Graph Exploration Space Lower Bounds

• Pierre Fraigniaud
• David Ilcinkas
• Sergio Rajsbaum
• Sébastien Tixeuil
Chapter
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3895)

## 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.

## Keywords

Undirected Graph Edge Incident Directed Cycle Parallel Edge Graph Exploration
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

1. 1.
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)Google Scholar
2. 2.
Bhatt, S.N., Even, S., Greenberg, D.S., Tayar, R.: Traversing Directed Eulerian Mazes. J. Graph Algorithms Appl. 6(2), 157–173 (2002)
3. 3.
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)
4. 4.
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)Google Scholar
5. 5.
Budach, L.: Automata and labyrinths. Math. Nachrichten, 195–282 (1978)Google Scholar
6. 6.
Cook, S., Rackoff, C.: Space lower bounds for maze threadability on restricted machines. SIAM J. on Computing 9(3), 636–652 (1980)
7. 7.
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)Google Scholar
8. 8.
Dudek, G., Jenkins, M., Milios, E., Wilkes, D.: Robotic Exploration as Graph Construction. IEEE Transaction on Robotics and Automation 7(6), 859–865 (1991)
9. 9.
Even, S., Itkis, G., Rajsbaum, S.: On Mixed Connectivity Certificates. Theor. Comput. Sci. 203(2), 253–269 (1998)
10. 10.
Even, S., Litman, A., Winkler, P.: Computing with Snakes in Directed Networks of Automata. J. Algorithms 24(1), 158–170 (1997)
11. 11.
Even, S., Tarjan, R.E.: Computing an st -Numbering. Theor. Comput. Sci. 2(3), 339–344 (1976)
12. 12.
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)
13. 13.
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)
14. 14.
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)Google Scholar
15. 15.
Reingold, O.: Undirected ST-Connectivity in Log-Space. To appear in 37th ACM Symp. on Theory of Computing, STOC (2005)Google Scholar
16. 16.
Rollik, H.-A.: Automaten in planaren graphen. Acta Informatica 13, 287–298 (1980)
17. 17.
Shannon, C.-E.: Presentation of a Maze-Solving Machine. In: 8th Conf. of the Josiah Macy Jr. Found (Cybernetics), pp. 173–180 (1951)Google Scholar

## Authors and Affiliations

• Pierre Fraigniaud
• 1
• David Ilcinkas
• 2
• Sergio Rajsbaum
• 3
• Sébastien Tixeuil
• 4
1. 1.CNRS, LRIUniversité Paris-SudFrance
2. 2.LRIUniversité Paris-SudFrance
3. 3.Instituto de MatemáticasUniv. Nacional Autónoma de MéxicoMexico
4. 4.LRI & INRIAUniversité Paris-SudFrance