Temporal Exploration of Random Spanning Tree Models

The Temporal Graph Exploration problem (TEXP) takes as input a temporal graph, i.e., a sequence of graphs (G i ) i∈N 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 i . If each such G i is connected, then an exploration of length n 2 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 1 (w.h.p.), be explored in O(n 3/2 ) 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.