Brief Announcement: Exploration of Always $S$-Connected Temporal Graphs

In many real-world settings, networks are not static objects but instead have unstable connections that vary over time. Such examples include public transport networks [15] and infection control [18]. Temporal graphs provide a model for such time-varying networks. Formally, a temporal graph $𝒢$ is a generalisation of (static) graphs containing a common vertex set $V$ and ordered sequence of $T$ snapshots $G_1,G_2,\mathrm{\dots },G_T$, with the lifetime of the graph defined by the number of snapshots, by convention denoted $T$. Unlike some models of dynamic graphs, we assume that we have full knowledge of the graph, i.e. that we are given every snapshot as part of the input.

Much work on temporal graphs has focused on the problem of exploration of temporal graphs. In the temporal exploration problem, denoted TEXP, every vertex must be visited at least once by one of a set of agents. The movement of the agents is restricted by allowing only a single move per snapshot. Thus, as the graph changes, the agents’ movement may become restricted. We assume our objective is to find a set of temporal walks, a generalisation of walks accounting for the movement restrictions imposed by only traversing a single edge per snapshot, covering the vertex set, with exactly one walk per agent. We call such a set of walks an exploration schedule.

Work on TEXPwas motivated by extending the well-known Travelling Salesman to temporal graphs by Michail and Spirakis [17]. Since then, there has been a broad span of work covering reachability [8, 10, 16] and exploration [1, 4, 5, 9, 11, 12, 13, 14, 15, 17]. The decision version of TEXP in which one has to decide if at least one exploration schedule exists in a given temporal graph from a given starting vertex is an NP-complete problem [17]. Indeed, this problem remains NP-complete even if the underlying graph has pathwidth 2 and every snapshot is a tree [7], or if the underlying graph is a star and the exploration has to start and end at the centre of the star [3]. In the optimisation version of this problem, we ask for the quickest exploration of a given temporal graph, that being the schedule ending at the earliest snapshot, formally defined in Section 2.

On the positive side, we mention the landmark paper by Erlebach et al. [11], who show that any always-connected temporal graph (temporal graphs where each snapshot is connected) can be explored in $O(n^2)$ snapshots, where $n$ is the number of vertices. This has recently been improved by Bastide et al. [6], who have shown that the always-connected temporal graphs with average degree $\mathrm{\Delta }$ can be explored in $O(n^{3/2}\sqrt{\mathrm{\Delta }\log n})$ snapshots, simplifying to $O(n^{3/2}\sqrt{\log n})$ for graphs of constant average degree, such as planar graphs, and to $O(n^{3/2}\sqrt{k\log n})$ for graphs of treewidth $k$. At the same time, Baguley et al. [5] have shown that if each snapshot is a random spanning tree of the graph, then, regardless of the degree, the graph can, with high probability, be explored in the lower of $O(n^{3/2})$ or $O(m)$ snapshots, where $n$ is the number of vertices and $m$ the number of edges.

We first define the notation used in this paper. Let $[i,j]=i,i+1,\mathrm{\dots },j$ denote the (ordered) set of integers between some pair $i,j\in \mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers. Note that if $i=j$, then $[i,j]=\{i\}$, and if $i>j$, $[i,j]=\mathrm{\varnothing }$. For notational conciseness, we us $[i]$ as shorthand for $[1,i]$.

We define a graph $G=(V,E)$ by a set of vertices, by convention $V=\{v_1,v_2,\mathrm{\dots },v_n\}$, and a set of edges, by convention $E\subseteq V\times V$, each a tuple of vertices. Note that we may write the edge $e$ between the vertices $v_i$ and $v_j$ as either $e=(v_i,v_j)$ or $e=(v_j,v_i)$. When an edge is given explicitly as $(v_i,v_j)$, we call $v_i$ the start point and $v_j$ the end point. A walk in a graph is an ordered sequence of edges $W=(v_{i_1},v_{i_2}),(v_{i_2},v_{i_3}),\mathrm{\dots },(v_{i_{m-1},v_{i_m}})$, where the end point of the $j^{th}$ edge is the start point of the ${(j+1)}^{th}$ edge. The start point of the first edge in a given walk is the start point of the walk and, analogously, the end point of the walk is the end point of the last edge in the walk. The length of a walk $W$, denoted $|W|$ is the number of edges in the walk. A graph $G=(V,E)$ is connected if there exists, for every pair of vertices $v,u\in V$, a walk starting at $v$ and ending at $u$. Note that a single walk $W$ may contain multiple copies of the same edge without contradiction. On the other hand, a path is a walk where no vertex is in more than two edges, and both the start and end vertices belong to a single edge, the first and last respectively.

A temporal graph is a generalisation of a graph, herein called a static graph whenever confusion may otherwise arise, where, rather than having a single edge set, the graph contains an ordered sequence of snapshots, by convention $G_1,G_2,\mathrm{\dots },G_T$, each of which is a static graph over a shared set of vertices. We assume that $G_t=(V,E_t)$, for every $t\in [1,T]$. An edge $e$ is active at snapshot $t$ if $e\in E_t$. In our definition, an edge $e$ may be active in any number of snapshots.

The underlying graph of a temporal graph $𝒢=G_1,G_2,\mathrm{\dots },G_T$, denoted $U(𝒢)$, is the static graph $U(𝒢)=(V,{\bigcup }_{t\in [1,T]}{E}_t)$, i.e. the static graph formed with the edge set corresponding to the union of all snapshots in the graph. For simplicity, given a vertex $v$ in a temporal graph $𝒢$ we use $\mathrm{\Delta }(v)$ to denote the neighbourhood of $v$ in the underlying graph $U(𝒢)$. A temporal graph $𝒢=G_1,G_2,\mathrm{\dots },G_T$ is an always-connected temporal graph if the static graph $G_t$ is connected, for every $t\in [T]$.

In this section, we provide our primary result, namely that any always $S$-connected graph can be explored by $m=|S|$ agents in at most $O\left(n^{3/2}{m}^3{\mathrm{\Delta }}^{3/2}{\log }^{3/2}n\right)$ snapshots, where $\mathrm{\Delta }$ is the average degree of any vertex in the underlying graph, i.e. $\mathrm{\Delta }={\sum }_{v\in V}\mathrm{\Delta }(v)/|V|$. We note this directly generalises the results from [6], with the key difference being the generalisation from always-connected temporal graphs to always $S$-connected temporal graphs.

We assume, for the remainder of this section, that $S$ contains $m$ vertices, that the temporal graph contains $n$ vertices, and that the average degree of the underlying graph is $\mathrm{\Delta }$. We will restate this notation within the key theorems of this section. We begin with a small Lemma that provides an immediate tool for exploring such graphs in $O(n^{2}m)$ snapshots.

Note that Lemma 6 allows for an exploration of any always $S$-connected temporal graph in $O(n^{2}m)$ snapshots by exploring each vertex, one after another, each requiring $O(nm)$ snapshots, with the key property that, after exploring a given vertex, the agent returns to its starting vertex in $S$, allowing the repeated application of the lemma. We now provide our key combinatorial tools for lowering the upper bound on the number of snapshots needed to explore the graph, based on those provided in [6], for exploring always $S$-connected temporal graphs with a fixed number of components defined by a subset of vertices.

We can now prove our main result. At a high level, we combine Lemmas 9 and 10 to explore the set of unvisited vertices in an iterative manner, exploring $\sqrt{|X^{\prime }|/(\mathrm{\Delta }\log |X^{\prime }|)}/16m$ in each epoch, while maintaining the key property that, after each exploration, we have exactly one agent on each vertex in $S$. This way, we allow ourselves to repeatedly apply the same approach in each epoch to an increasingly small number of vertices, until we are left with some set of $O(m^2)$, which we may explore via Lemma 6 in $O(n{m}^3)$ snapshots.

We now adapt the results from [1] to provide improved bounds on the exploration of graphs of bounded treewidth. First, we provide a bound on the number of snapshots needed to explore always-connected temporal graphs whose underlying graph contains an $(r,b)$-division.