Temporal Exploration of Random Spanning Tree Models

Baguley, S, Göbel, A, Klodt, N, Skretas, G, Sylvester, J ORCID: 0000-0002-6543-2934 and Zamaraev, V ORCID: 0000-0001-5755-4141 (2026) Temporal Exploration of Random Spanning Tree Models In: 37th ACM-SIAM Symposium on Discrete Algorithms (SODA 2026).

Text TemporalExpanders (1).pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (540kB) | Preview

Abstract

The Temporal Graph Exploration problem (TEXP) takes as input a temporal graph, i.e., a sequence of graphs (G<inf>i</inf>)<inf>i∈ℕ</inf> on the same vertex set, and asks for a walk of shortest length visiting all vertices, where the i-th step uses an edge from G<inf>i</inf> or stays put. If each such G<inf>i</inf> is connected, then an exploration of length n² exists, and this is known to be the best possible up to a constant. More fine-grained lower and upper bounds have been obtained for restricted temporal graph classes, however, for several fundamental classes, a large gap persists between known bounds, and it remains unclear which properties of a temporal graph make it inherently difficult to explore. Motivated by this limited understanding and the central role of the Temporal Graph Exploration problem in temporal graph theory, we study the problem in a randomised setting. We introduce the Random Spanning Tree (RST) model, which consists of a set of n-vertex trees together with an arbitrary probability distribution µ over this set. A random temporal graph generated by the RST model is a sequence of independent samples drawn from µ. We initiate a systematic study of the Temporal Graph Exploration problem in such random temporal graphs and establish tight general bounds on exploration time. Our first main result proves that any RST model can, with high probability¹ (w.h.p.), be explored in O(n³/²) time, and we show that this bound is tight up to a constant factor. This demonstrates a fundamental difference between the adversarial and random settings. Our second main result shows that if all trees of an RST are subgraphs of a fixed graph with m edges, then, w.h.p., it can be explored in O(m) time.

Item Type:	Conference Item (Unspecified)
Divisions:	Faculty of Science & Engineering Faculty of Science & Engineering > School of Computer Science & Informatics Faculty of Science & Engineering > School of Computer Science & Informatics > Algorithms and Computing Systems
Depositing User:	Symplectic Admin
Date Deposited:	27 Jan 2026 08:35
Last Modified:	16 Apr 2026 02:07
DOI:	10.1137/1.9781611978971.106
Related Websites:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3195010
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.