Exploration on highly dynamic graphs

Abstract We study the exploration problem by mobile agents in two prominent models of dynamic graphs: 1-Interval Connectivity and T-Connectivity Time. The 1-Interval Connectivity model was introduced by Kuhn et al. [STOC 2010], and the T-Connectivity Time model was proposed by Michail et al. [JPDC 2014]. Recently, Saxena et al. [TCS 2025] investigated the exploration problem under both models. In this work, we first strengthen the existing impossibility results for 1-Interval Connected dynamic graphs. We then show that, in T-Connectivity Time dynamic graphs, exploration is impossible with \(\frac{(n-1)(n-2)}{2}\) mobile agents, even when the agents have full knowledge of all system parameters, global communication, full visibility, and infinite memory. This significantly improves the previously known bound of n. Moreover, we prove that to solve exploration with \(\frac{(n-1)(n-2)}{2}+1\) agents, 1-hop visibility is necessary. Finally, we present an exploration algorithm that uses \(\frac{(n-1)(n-2)}{2}+1\) agents, assuming global communication, 1-hop visibility, and \(O(\log n)\) memory per agent. Similar content being viewed by others Data availability No datasets were generated or analysed during the current study. Notes Note that if exploration is impossible, then perpetual exploration is also impossible, and if perpetual exploration is possible, then exploration is also possible. This step does not introduce any new holes or edges incident to holes during Phase 2; it only records the ports at node \(w_1\) that lead to a hole. For a path \(P=v_1\sim v_2\sim \cdots \sim v_t\), let \(\sigma (P)=(p_1,p_2,\ldots ,p_{t-1})\), where \(p_i\) is the port number at \(v_i\) corresponding to the edge \((v_i,v_{i+1})\). Among multiple shortest paths, the lexicographically shortest path is the one whose port sequence is lexicographically minimum. References Saxena, A., Mondal, K.: Natural calamities demand more rescuers: exploring connectivity time dynamic graphs. In: 39th International Symposium on Distributed Computing (DISC 2025), Vol. 356 (2025 Shannon, C.E.: Presentation of a maze-solving machine, Claude Elwood Shannon Collected Papers (1993) Albers, S., Henzinger, M.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164–1188 (2000) Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. ACM Trans. Algorithms 4(4), 1–18 (2008) Chalopin, J., Flocchini, P., Mans, B., Santoro, N.: Network exploration by silent and oblivious robots. In: Proc. of 36th International Workshop on Graph-Theoretic Concepts in Computer Science (WG) (2010) Deng, X., Papadimitriou, C.: Exploring an unknown graph. J. Graph Theory 32(3), 265–297 (1999) Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33, 281–295 (1999) Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theoret. Comput. Sci. 345(2–3), 331–344 (2005) Fraigniaud, P., Ilcinkas, D., Pelc, A.: Impact of memory size on graph exploration capability. Discret. Appl. Math. 156(12), 2310–2319 (2008) Dieudonné, Y., Pelc, A.: Deterministic network exploration by anonymous silent agents with local traffic reports. ACM Trans. Algorithms 11(2), 1–29 (2014) Dobrev, S., Narayanan, L., Opatrny, J., Pankratov, D.: Exploration of high-dimensional grids by finite automata. In: Proc. of 46th Int. Colloquium on Automata, Languages, and Programming (ICALP) (2019) Das, S.: Graph exploration with mobile agents. In: Chapter 16 of Handbook of Graph Theory, Combinatorial Optimization, and Algorithms (2019) Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 513–522. Association for Computing Machinery, New York (2010) Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. 27(5), 387–408 (2012) Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Causality, influence, and computation in possibly disconnected synchronous dynamic networks. J. Parallel Distrib. Comput 74(1), 2016–2026 (2014) Augustine, J., Moses, W.K.: Dispersion of mobile robots: a study of memory-time trade-offs, ICDCN ’18 (2018) Kshemkalyani, A.D., Molla, A.R., Sharma, G.: Efficient dispersion of mobile robots on dynamic graphs, in: ICDCS 2020, pp. 732–742 (2020) Fraigniaud, P., Gasieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks 48(3), 166–177 (2006) Agarwalla, A., Augustine, J., Moses, W.K., Madhav, S.K., Sridhar, A.K.: Deterministic Dispersion of Mobile Robots in Dynamic rings, ICDCN ’18. Association for Computing Machinery, New York (2018) Miller, A., Saha, U.: Fast byzantine gathering with visibility in graphs. In: Pinotti, C.M., Navarra, A., Bagchi, A. (eds.) Algorithms for Sensor Systems, pp. 140–153. Springer International Publishing, Cham (2020) Flocchini, P., Kellett, M., Mason, P.C., Santoro, N.: Searching for black holes in subways. Theory Comput. Syst 50, 158–184 (2012) Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) Automata, Languages, and Programming, pp. 444–455. Springer, Berlin, Heidelberg (2015) Erlebach, T., Spooner, J.T.: Faster exploration of degree-bounded temporal graphs (2018) Erlebach, T., Kammer, F., Luo, K., Sajenko, A., Spooner, J.T.: Two moves per time step make a difference. In: ICALP 2019, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, p. 141 (2019) Ilcinkas, D., Wade, A.M.: Exploration of the t-interval-connected dynamic graphs: the case of the ring. Theory Comput. Syst. 62, 1144–1160 (2018) Ilcinkas, D., Klasing, R., Wade, A.M.: Exploration of constantly connected dynamic graphs based on cactuses. In: International Colloquium on Structural Information and Communication Complexity, pp. 250–262. Springer (2014) Avin, C., Kouckỳ, M., Lotker, Z.: How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In: ICALP 2008, pp. 121–132. Springer (2008) Flocchini, P., Mans, B., Santoro, N.: On the exploration of time-varying networks. Theor. Comput. Sci. 469, 53–68 (2013) Ilcinkas, D., Wade, A.M.: On the power of waiting when exploring public transportation systems. In: OPODIS 2011, pp. 451–464. Springer (2011) Bournat, M., Datta, A.K., Dubois, S.: Self-stabilizing robots in highly dynamic environments. In: SSS 2016, pp. 54–69. Springer (2016) Bournat, M., Dubois, S., Petit, F.: Computability of perpetual exploration in highly dynamic rings. In: ICDCS 2017, IEEE, pp. 794–804 (2017) Di Luna, G., Dobrev, S., Flocchini, P., Santoro, N.: Distributed exploration of dynamic rings. Distrib. Comput. 33, 41–67 (2020) Gotoh, T., Sudo, Y., Ooshita, F., Kakugawa, H., Masuzawa, T.: Group exploration of dynamic tori. In: ICDCS 2018, IEEE, pp. 775–785 (2018) Gotoh, T., Sudo, Y., Ooshita, F., Masuzawa, T.: Exploration of dynamic ring networks by a single agent with the h-hops and s-time steps view, In: SSS, Springer (2019) Gotoh, T., Flocchini, P., Masuzawa, T., Santoro, N.: Exploration of dynamic networks: tight bounds on the number of agents. J. Comput. Syst. Sci. 122, 1–8 (2021) Saxena, A., Mondal, K.: Path connected dynamic graphs with a study of dispersion and exploration. Theor. Comput. Sci. 1050, 115390 (2025) Acknowledgements Ashish Saxena would like to acknowledge the financial support from IIT Ropar. Kaushik Mondal would like to acknowledge the ISIRD grant provided by IIT Ropar. This work was partially supported by the FIST program of the Department of Science and Technology, Government of India, Reference No. SR/FST/MS-I/2018/22(C). We thank the anonymous reviewers for their careful reading and insightful comments, which helped improve the presentation and quality of this paper. In particular, their suggestions led us to strengthen and clarify the analysis of our algorithm, resulting in a more rigorous and complete exposition of the results. Author information Authors and Affiliations Contributions Ashish Saxena: Conceptualization; Methodology; Formal analysis and investigation; Writing—original draft preparation; Writing—review and editing. Kaushik Mondal: Conceptualization; Verification; Writing—review and editing; Supervision. Corresponding author Ethics declarations Competing interests The authors declare no competing interests. Generative AI and AI-assisted technologies in the writing process During the preparation of this work, we used Grammarly, ChatGPT tools in order to improve language quality. After using this tool, we reviewed and edited the content as needed and take full responsibility for the content of the publication. Additional information Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. A preliminary version of this work appeared in DISC 2025 [1]. Rights and permissions Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law. About this article Cite this article Saxena, A., Mondal, K. Exploration on highly dynamic graphs. Distrib. Comput. 39, 23 (2026). https://doi.org/10.1007/s00446-026-00516-z Received: Accepted: Published: Version of record: DOI: https://doi.org/10.1007/s00446-026-00516-z