Brief Announcement: The Shortest Temporal Exploration Problem

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 $𝒢$ of lifetime $L$ may be defined as a sequence of undirected graphs $(G_1,G_2,\mathrm{\dots },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].
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 annoucement the proofs are omitted because of the limited number of pages. A complete version with proofs can be found online.

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.

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

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.

In the rest of the paper we consider that $𝒢$ is a constantly connected tempoal graph i.e. every snapshot is connected and $s$ is the starting vertex for the exploration. The notation $u{\rightsquigarrow }_{r}v$ is used for a journey from $u$ to $v$ in $𝒢$ whose length is less than or equal to $r$. Similarly, for a snapshot $G_i$ of $𝒢$ 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$.

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

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 . A sufficient condition for the existence of a journey of at most $k$ edges from $u$ to $v$ is first given.

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$.

The idea of the proof is that, given the set of unvisited vertices $S$ and a time-window of size $\mathrm{\Theta }(\sqrt{|S|}{n}^2)$, for every integer 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 , $|X(S)|$ is $O(n/k)$ in the time-window of size $\mathrm{\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).

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 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.

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 $\mathrm{\Omega }(n^2)$ time steps with $\mathrm{\Omega }(n)$ edges traversed. We have proven that, for each temporal graph with $L=\mathrm{\Theta }(n^2)$, there is an exploration in $O(n^2)$ time steps and $O(n)$ edges traversed if each snapshot of $𝒢$ has a bounded diameter. Hence our bounds are tight.

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

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.