Abstract
We study a very restrictive graph exploration problem. In our model, an agent without persistent memory is placed on a vertex of a graph and only sees the adjacent vertices. The goal is to visit every vertex of the graph, return to the start vertex, and terminate. The agent does not know through which edge it entered a vertex. The agent may color the current vertex and can see the colors of the neighboring vertices in an arbitrary order. The agent may not recolor a vertex. We investigate the number of colors necessary and sufficient to explore all graphs. We prove that \(n-1\) colors are necessary and sufficient for exploration in general, 3 colors are necessary and sufficient if only trees are to be explored, and \(\min (2k-3,n-1)\) colors are necessary and \(\min (2k-1,n-1)\) colors are sufficient on graphs of size n and circumference k, where the circumference is the length of a longest cycle. Moreover, we prove that recoloring vertices is very powerful by designing an algorithm with recoloring that uses only 7 colors and explores all graphs.
Part of the work by Fabian Frei was done during a visit at Hosei University and supported by grant GR20109 by the Swiss National Science Foundation (SNSF) and the Japan Society for the Promotion of Science (JSPS).
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
Notes
- 1.
Note that this coloring is just a normal labeling and has nothing to do with graph coloring such as in 3-Coloring; it is perfectly fine to color adjacent vertices with the same color.
- 2.
Here, we use “time complexity” as the complexity of the algorithm that calculates the decisions of the agent and “competitive ratio” as the number of time steps of the agent compared to an optimal number of time steps.
- 3.
Note that the agent may have colored \(v_{i+1}\) and thus the environment of the second visit of \(v_i\) may be different from the environment of the first visit, leading to a potentially different decision.
- 4.
By predecessor of a vertex v that is not the root, we mean the neighbor w from which the agent moved to v when v was first visited.
References
Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. ACM Trans. Algorithms 4(4), 42:1–42:18 (2008). https://doi.org/10.1145/1383369.1383373
Das, S.: Graph explorations with mobile agents. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities, Current Research in Moving and Computing. LNCS, vol. 11340, pp. 403–422. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-7_16
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, 5th edn. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-53622-3
Disser, Y., Hackfeld, J., Klimm, M.: Tight bounds for undirected graph exploration with pebbles and multiple agents. J. ACM 66(6), 40:1–40:41 (2019). https://doi.org/10.1145/3356883
Gąsieniec, L., Radzik, T.: Memory efficient anonymous graph exploration. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 14–29. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92248-3_2
Menc, A., Pajak, D., Uznanski, P.: Time and space optimality of rotor-router graph exploration. Inf. Process. Lett. 127, 17–20 (2017). https://doi.org/10.1016/j.ipl.2017.06.010
Acknowledgments
We thank the anonymous reviewers for their useful suggestions for improvement.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Böckenhauer, HJ., Frei, F., Unger, W., Wehner, D. (2023). Zero-Memory Graph Exploration with Unknown Inports. In: Rajsbaum, S., Balliu, A., Daymude, J.J., Olivetti, D. (eds) Structural Information and Communication Complexity. SIROCCO 2023. Lecture Notes in Computer Science, vol 13892. Springer, Cham. https://doi.org/10.1007/978-3-031-32733-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-32733-9_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-32732-2
Online ISBN: 978-3-031-32733-9
eBook Packages: Computer ScienceComputer Science (R0)