Sparse Temporal Spanners with Low Stretch

A temporal graph is an undirected graph G = (V,E) along with a function λ : E → N+ that assigns a time-label to each edge in E. A path in G such that the traversed time-labels are non-decreasing is called a temporal path. Accordingly, the distance from u to v is the minimum length (i.e., the number of edges) of a temporal path from u to v. A temporal α-spanner of G is a (temporal) subgraph H that preserves the distances between any pair of vertices in V , up to a multiplicative stretch factor of α. The size of H is measured as the number of its edges. In this work, we study the size-stretch trade-offs of temporal spanners. In particular we show that temporal cliques always admit a temporal (2k -1)-spanner with eO(kn1+1k ) edges, where k > 1 is an integer parameter of choice. Choosing k = log n⌉, we obtain a temporal O(log n)-spanner with eO(n) edges that has almost the same size (up to logarithmic factors) as the temporal spanner given in [Casteigts et al., JCSS 2021] which only preserves temporal connectivity. We then turn our attention to general temporal graphs. Since Ω(n2) edges might be needed by any connectivity-preserving temporal subgraph [Axiotis et al., ICALP'16], we focus on approximating distances from a single source. We show that eO(n/ log(1 + ϵ)) edges suffice to obtain a stretch of (1 + ϵ), for any small ϵ > 0. This result is essentially tight in the following sense: There are temporal graphs G for which any temporal subgraph preserving exact distances from a single-source must use Ω(n2) edges. Interestingly enough, our analysis can be extended to the case of additive stretch for which we prove an upper bound of eO(n2/β) on the size of any temporal β-additive spanner, which we show to be tight up to polylogarithmic factors. Finally, we investigate how the lifetime of G, i.e., the number of its distinct time-labels, affects the trade-off between the size and the stretch of a temporal spanner.