# Brief Announcement : The Shortest Temporal Exploration Problem

Stefan Balev, Éric Sanlaville, Antoine Toullalan

► To cite this version:

Stefan Balev, Éric Sanlaville, Antoine Toullalan. Brief Announcement: The Shortest Temporal Exploration Problem. Symposium on Algorithmic Foundations of Dynamic Networks (SAND), Jun 2025, LIVERPOOL, United Kingdom. 10.4230/LIPIcs.SAND.2025.2. hal-05283832

HAL Id: hal-05283832

https://normandie-univ.hal.science/hal-05283832v1

Submitted on 25 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Brief Announcement: The Shortest Temporal Exploration Problem

Stefan Balev

<figure><img src="image_2.png" /></figure>

Université Le Havre Normandie, Univ Rouen Normandie, INSA Rouen Normandie, Normandie
Univ, LITIS UR 4108, F-76600 Le Havre, France

Éric Sanlaville

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

Université Le Havre Normandie, Univ Rouen Normandie, INSA Rouen Normandie, Normandie
Univ, LITIS UR 4108, F-76600 Le Havre, France

Antoine Toullalan

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

Université Le Havre Normandie, Univ Rouen Normandie, INSA Rouen Normandie, Normandie
Univ, LITIS UR 4108, F-76600 Le Havre, France

## Abstract

A temporal graph is a graph for which the edge set can change from one time step to the next. This paper considers undirected temporal graphs defined over $L$ time steps and connected at each time step. We study the Shortest Temporal Exploration Problem (STEXP) that, given the evolution of the graph, asks for a temporal walk that starts at a given vertex, moves over at most one edge at each time step, visits all the vertices, takes at most $L$ time steps and traverses the smallest number of edges. We prove that every constantly connected temporal graph with $n$ vertices can be explored with $O(n^{1.5})$ edges traversed if $L$ is $O(n^{3.5})$ time steps. This result improves the upper bound of $O(n^2)$ edges when $L$ is $\Omega(n^2)$. Moreover, we study the case where the graph has a diameter bounded by a parameter $k$ at each time step and we prove that there exists an exploration which takes $O(kn^2)$ time steps and traverses $O(kn)$ edges. Finally, the case where the underlying graph is a cycle is studied and tight linear bounds are provided on the number of edges traversed in the worst-case.

2012 ACM Subject Classification Mathematics of computing → Graph theory

Keywords and phrases Graph Theory, Temporal Graph, Temporal Graph Exploration

Digital Object Identifier 10.4230/LIPIcs.SAND.2025.18

Related Version Full Version: https://doi.org/10.48550/arXiv.2504.06652

Funding This work was Supported by the French ANR, project ANR-22-CE48-0001 (TEMPOGRAL).

## 1 Introduction

Many real-life networks are not static objects because their connections may vary over time (e.g. transportation, communication, social interactions,...). A tool to modelize and study these networks is temporal graphs whose edge set changes over time. More formally, a temporal graph $\mathcal{G}$ of lifetime $L$ may be defined as a sequence of undirected graphs $(G_1, G_2, ..., G_L)$ called *snapshots*. The adaptation of path-related problems from static graphs to temporal graphs raises several questions: mainly, the notion of path itself, and the optimization criteria to use. In a static graph, a set of edges connecting two vertices $u$ and $v$ is called a *path* between $u$ and $v$, but in a temporal graph the equivalent is a *journey* from $u$ to $v$ which is a sequence of edges successive in time from $u$ to $v$. It follows that, in temporal graphs, at least three criteria may be minimized when considering journeys: the *length* (the number of edges), the *arrival time* and the *duration* (the difference between the arrival time and the starting time of the agent). An extensive study of these criteria in temporal graphs can be found in the article of Bui-Xuan et al.[4].

<figure><img src="image_7.png" /></figure>

© Stefan Balev, Éric Sanlaville, and Antoine Toullalan;

licensed under Creative Commons License CC-BY 4.0

4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025).

Editors: Kitty Meeks and Christian Scheideler; Article No. 18; pp. 18:1–18:5

<figure><img src="image_8.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
18:2 Brief Announcement: The Shortest Temporal Exploration Problem

A well studied path-related problem in temporal graphs is the exploration problem introduced by Michail and Spirakis[3] which aims at finding a journey that visits all the vertices starting from a given vertex. They make the assumption that the graph is connected at each time step and that the agent already knows the evolution of the graph because it guarantees that an exploration exists if the lifetime $L$ is greater than $|V|^2$ where $V$ is the vertex set. Most following papers studied the Temporal Exploration Problem (TEXP) which, given the evolution of the graph, starts at a given vertex and aims at minimizing the *arrival time* under the assumption that the graph is constantly connected [1]. We denote the Shortest Temporal Exploration Problem (STEXP) the Temporal Exploration Problem which, under the same hypothesis, aims at minimizing the *number of edges traversed*. The static graph whose edge set is the union of the edge sets of each snapshot is denoted the *underlying graph* and the total number of vertices is denoted by $n$. To the best of our knowledge no specific study exists on the STEXP. In this brief announcement the proofs are omitted because of the limited number of pages. A complete version with proofs can be found online.

2 Preliminaries

**Definition 1 (Temporal graph).** A temporal graph $\mathcal{G}$ with a vertex set $V_G$ and a lifetime $L_G$ is a sequence of static graphs $(G_1, G_2, ... G_{L_G})$ where $G_i = (V_G, E_i)$ is called the snapshot at the time step $i \in [1, L_G]$. The underlying graph of $\mathcal{G}$ is $G = (V_G, E)$ with $E$ the union of the edge sets of all the snapshot of $\mathcal{G}$.

In the rest of the paper, if no ambiguity arises, we will note the lifetime by $L$ and the vertex set by $V$. We restrict our attention to always-connected graph. Moreover, when talking about journeys, we often refer to an agent that is supposed to traverse the edges of the journey.

**Definition 2 (Path).** Let $\mathcal{G}$ be a temporal graph. A path between the vertices $u \in V$ and $v \in V$ is a set of edges all belonging to the same snapshot and connecting $u$ and $v$.

We highlight the fact that a path is associated to exactly one snapshot.

**Definition 3 (Journey).** Let $\mathcal{G}$ be a temporal graph. A journey from $u \in V$ to $v \in V$ is a sequence of edges of increasing time steps (not necessarily consecutive), [((v₀, v₁), t₁), ((v₁, v₂), t₂), ..., (vᵢ₋₁, vᵢ), tᵢ)], where (vᵢ, vᵢ₊₁) ∈ Eᵢ, v₀ = u and vᵢ = v. So an agent can go from u to v by traversing the edges of the sequence at the time step indicated. There exist two types of journeys:

- the non-strict journeys where the agent can traverse several edges per time step.

- the strict journeys where the agent can traverse at most one edge per time step, i.e. $\forall i < l, t_i < t_{i+1}$.

Since constantly connected temporal graphs are studied, if non-strict journeys were allowed, there would be an exploration in 1 time step with at most $2n - 3$ edge traversals. So only strict journeys are considered which means that at each time step the agent can either stay on a vertex or traverse an edge.

**Definition 4 (Journey parameters).** Let $\mathcal{G}$ be a temporal graph and the journey $J = ((e_1, t_1), (e_2, t_2), ..., (e_k, t_k))$ in $\mathcal{G}$.

- **Length**
The length of $J$ is the number of edges of the journey, i.e. $k$.

- **Arrival time**
The arrival time is the time step where the agent traverses the last edge that is $t_k$.

- **Duration**
The duration is the number of time steps of the journey which is $t_k - t_1 + 1$.
**► Definition 5** (Shortest Temporal Exploration Problem (STEXP)). *Given a temporal graph $\mathcal{G}$ with a lifetime $L$ and a starting vertex $s$, STEXP asks for a journey in $\mathcal{G}$ starting on $s$ that visits all the vertices of the graph and has a minimum length.*

In the rest of the paper we consider that $\mathcal{G}$ is a constantly connected temporal graph i.e. every snapshot is connected and $s$ is the starting vertex for the exploration. The notation $u \rightsquigarrow v$ is used for a journey from $u$ to $v$ in $\mathcal{G}$ whose length is less than or equal to $r$. Similarly, for a snapshot $G_i$ of $\mathcal{G}$ we note $u \leftrightarrow r v$ a path connecting $u$ and $v$ with a number of edges less than or equal to $r$ in $G_i$.

**► Lemma 6** (Reachability[3]). *Let $\mathcal{G}$ be a temporal graph of lifetime $L \ge n-1$ and $(u,v)$ a pair of vertices. Then $\forall t \le L-n+2$ there is a strict journey from $u$ to $v$ starting at $t$, whose duration is at most $n-1$.*

This lemma implies the following result: considering any temporal graph $\mathcal{G}$, there is an exploration with an arrival time (and length) inferior or equal to $n(n-1)$.

### 3 The STEXP in the general case

Recall that our assumption is that each snapshot is connected and the agent already knows the evolution of the graph.

Let $(u, v)$ be a pair of vertices and $k, 1 \le k < n$. A sufficient condition for the existence of a journey of at most $k$ edges from $u$ to $v$ is first given.

**► Lemma 7.** Let $\mathcal{G}$ be a temporal graph of $n$ vertices (not necessarily connected at each time steps) and $k$ such that $1 \le k < n$, the lifetime of the graph is $L \ge kn$.

Let $u, v$ be two distinct vertices of $V$, such that there exist $kn$ distinct paths (i.e on distinct snapshots) with a number of edges less than or equal to $k$ connecting $u$ and $v$, each of these paths $u \leftrightarrow_k v$ is associated with exactly one time step. Then there exists a journey $u \rightsquigarrow_k v$ in $\mathcal{G}$ using only these time steps.

This lemma links the existence of paths of bounded lengths to the existence of one journey of bounded length between two vertices. With this lemma we can create a journey which is a concatenation of journeys of at most $k$ edges such that each one visits a different vertex of $S$.

**► Lemma 8.** Let $\mathcal{G}$ be a temporal graph with $S$ a subset of vertices. Then there exists a journey visiting $O(\sqrt{|S|})$ vertices of $S$ in $O(n^2|S|)$ timesteps with $O(n)$ edge traversals.

The idea of the proof is that, given the set of unvisited vertices $S$ and a time-window of size $\Theta(\sqrt{|S|n^2})$, for every integer $k < n$ we can create a subset of $S$ denoted $X(S)$ with the following property: for every vertex $v$ of $S$, there is a vertex $u$ of $X(S)$ such that there is a journey $u \rightsquigarrow_k v$. By Lemma 7, we have that for any subset $S$ and any integer $k < n$, $|X(S)|$ is $O(n/k)$ in the time-window of size $\Theta(\sqrt{|S|n^2})$. So, given $S$ and $k$, we create a journey that is a concatenation of shorter journeys (each traversing $k$ edges), each visiting a vertex of $S$ that belongs to a set $X(S)$ (each time the agent traverses one of these journeys with $k$ edges, the set $S$ is updated).

**► Theorem 9.** Let $\mathcal{G}$ be a temporal graph with a lifetime $L$ which is $\Omega(n^{3.5})$. Then there exists an exploration of $\mathcal{G}$ traversing $O(n^{1.5})$ edges in $O(n^{3.5})$ time steps.

The theorem 9 is a corollary of Lemma 8 because we create an exploration in $O(n^{1.5})$ edge traversals with the following method. Let $S$ be the set of unvisited vertices and $u$ be the vertex on which the agent is present at the current time step. Recall that the agent can go
<figure><img src="image_9.png" /><figcaption>■ **Figure 1** A representation of the concatenated journeys forming the journey that explores the graph in $O(n^{1.5})$ edges where each vertex represented is a vertex that is visited for the first time by the journey. The set of unvisited vertex is denoted $S$. A blue arrow is a journey traversing $n-1$ edges such as defined in the reachability lemma 6. And each purple arrow traverses at most $k$ edges which is $\Theta(n/\sqrt{S})$, a sequence of these types of journeys (between two journeys of $O(n)$ edges) represents a journey such as defined in Lemma 8 that traverses in total $O(n)$ edges and visit $\sqrt{S}$ vertices.</figcaption></figure>

to any vertex in $n-1$ time steps and by traversing at most $n-1$ edges by Lemma 6 so with
this type of journey the agent goes to the starting vertex of a journey such as defined in
the Lemma 8 that visits $\sqrt{|S|}$ unvisited vertices. After this journey we update the set of
unvisited vertices $S$ and reiterate the method until the agent visits all the vertices.
This concatenation of journeys forms the exploration such as presented in figure 1.

4 The case of bounded-diameter temporal graphs

**► Theorem 10.** Let $\mathcal{G} = (V, E_t), t \le L$ be a temporal graph of $n$ vertices and $0 < k < n$ an integer, the lifetime of the graph is $L \ge kn^2$. If $\forall t \le L$, the snapshot $G_t$ has a diameter less than or equal to $k$, then there exists an exploration of $\mathcal{G}$ traversing less than $kn$ edges.

The idea of the proof is that we can construct an exploration that visits all the vertices in an
arbitrary order starting from $s$. We visit an unvisited vertex every $kn$ time steps with at
most $k$ edge traversals because by assumption the distance between every pair of vertices is
at most $k$ every time step. So, by Lemma 7, in a time-window of size $kn$, there is a journey
traversing $k$ edges from the vertex on which the agent is present to the unvisited vertex. We
repeat this method $n-1$ times to visit all the vertices of the temporal graph.

Erlebach et al.[1] have presented a family of temporal graphs such that each snapshot
has a diameter 2 and all explorations take $\Omega(n^2)$ time steps with $\Omega(n)$ edges traversed. We
have proven that, for each temporal graph with $L = \Theta(n^2)$, there is an exploration in $O(n^2)$
time steps and $O(n)$ edges traversed if each snapshot of $\mathcal{G}$ has a bounded diameter. Hence
our bounds are tight.

5 The case of the cycle as the underlying graph

In this section the following notations are used: $\mathcal{C}$ is a temporal cycle which is a temporal graph whose underlying graph is a cycle, denoted $\mathcal{C}$.

**► Lemma 11.** Let $\mathcal{C}$ be a temporal cycle with a lifetime $L \ge 2n - 2$. In the worst-case scenario, the number of edges traversed for an exploration of $\mathcal{C}$ is exactly $\lfloor \frac{3}{2}(n-1) \rfloor$ edges.
**► Lemma 12.** For every integer $n \ge 3$, there exists a temporal cycle $C$ with $n$ vertices and a lifetime $L = 2n - 3$ such that there is only one possible exploration and this exploration traverses exactly $2n - 3$ edges.

An overview of the results described by lemmas 11 and 12 is presented in figure 2. Since Ilcinkas et al.[2] proved that there is always an exploration if and only if $L \ge 2n - 3$, we start the value of the lifetime at $2n - 3$ in figure 2. So the bounds are tight for the number of edges traversed in STEXP.

<figure><img src="image_10.png" /><figcaption>■ **Figure 2** A representation of the number of edges traversed in the worst case as a function of the lifetime $L$ for the temporal cycle.</figcaption></figure>

References

1. Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. *Journal of Computer and System Sciences*, 119:1–18, 2021. doi:10.1016/J.JCSS.2021.01.005.

2. David Ilcinkas and Ahmed Mouhamadou Wade. Exploration of the t-interval-connected dynamic graphs: the case of the ring. In *International Colloquium on Structural Information and Communication Complexity*, pages 13–23. Springer, 2013. doi:10.1007/978-3-319-03578-9_2.

3. Othon Michail and Paul G Spirakis. Traveling salesman problems in temporal graphs. *Theoretical Computer Science*, 634:1–23, 2016. doi:10.1016/J.TCS.2016.04.006.

4. Bui Xuan, Afonso Ferreira, and Aubin Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. *International Journal of Foundations of Computer Science*, 14(02):267–285, 2003. doi:10.1142/S0129054103001728.