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
Facts Only
* The study examines the exploration problem in two dynamic graph models: 1-Interval Connectivity and T-Connectivity Time.
* Impossibility results for 1-Interval Connected dynamic graphs are strengthened.
* Exploration is shown to be impossible in T-Connectivity Time dynamic graphs with $\frac{(n-1)(n-2)}{2}$ mobile agents, even with full knowledge and communication.
* Solving exploration with $\frac{(n-1)(n-2)}{2}+1$ agents necessitates 1-hop visibility.
* An algorithm for exploration is presented using $\frac{(n-1)(n-2)}{2}+1$ agents, assuming global communication, 1-hop visibility, and $O(\log n)$ memory per agent.
* The work references models introduced by Kuhn et al. [STOC 2010] and Michail et al. [JPDC 2014].
Executive Summary
Full Take
Sentinel — Human
This text exhibits the structured complexity, specific citation network, and authorial context typical of peer-reviewed academic research rather than synthetic generation.