Exploration of Random Temporal Graphs

1^st July 2025, 13:00 Ashton Lecture Theatre
Nicolas Klodt
Hasso Plattner Institute

Abstract

The temporal exploration problem (TEXP) asks for a walk in a given temporal graph, where at most one edge is traversed in each time step, and all vertices are visited. In this talk we will consider the temporal exploration problem (TEXP) on a model of random temporal graphs which are connected in each time step. It is known that there are n-vertex temporal graphs which are connected in each time step but require $\Omega(n^2)$ steps to explore, our aim is to understand what happens against a random adversary.

In our model an adversary supplies a measure $\mu$ supported on a set of (labelled) spanning trees on $n$ vertices, and we obtain a (random) temporal graph by sampling a spanning tree from $\mu$ at each time step independently. We show that, for any $\mu$, w.h.p. there is a schedule which explores the corresponding temporal graph in time $O(n^{3/2})$. Furthermore, we provide an example of $\mu$ which requires $\Omega(n^{3/2})$ steps to explore in expectation.

This is joint work with Samuel Baguley, Andreas Göbel, George Skretas, John Sylvester and Viktor Zamaraev