Bilò, Davide ;
D'Angelo, Gianlorenzo ;
Gualà, Luciano ;
Leucci, Stefano ;
Rossi, Mirko
Sparse Temporal Spanners with Low Stretch
Abstract
A temporal graph is an undirected graph G = (V,E) along with a function λ : E → ℕ^+ that assigns a timelabel to each edge in E. A path in G such that the traversed timelabels are nondecreasing 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 sizestretch tradeoffs of temporal spanners. In particular we show that temporal cliques always admit a temporal (2k1)spanner with Õ(kn^{1+1/k}) edges, where k > 1 is an integer parameter of choice. Choosing k = ⌊log n⌋, we obtain a temporal O(log n)spanner with Õ(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 Ω(n²) edges might be needed by any connectivitypreserving temporal subgraph [Axiotis et al., ICALP'16], we focus on approximating distances from a single source. We show that Õ(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 singlesource must use Ω(n²) edges. Interestingly enough, our analysis can be extended to the case of additive stretch for which we prove an upper bound of Õ(n² / β) 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 timelabels, affects the tradeoff between the size and the stretch of a temporal spanner.
BibTeX  Entry
@InProceedings{bilo_et_al:LIPIcs.ESA.2022.19,
author = {Bil\`{o}, Davide and D'Angelo, Gianlorenzo and Gual\`{a}, Luciano and Leucci, Stefano and Rossi, Mirko},
title = {{Sparse Temporal Spanners with Low Stretch}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {19:119:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772471},
ISSN = {18688969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16957},
URN = {urn:nbn:de:0030drops169575},
doi = {10.4230/LIPIcs.ESA.2022.19},
annote = {Keywords: temporal spanners, temporal graphs, graph sparsification, approximate distances}
}
01.09.2022
Keywords: 

temporal spanners, temporal graphs, graph sparsification, approximate distances 
Seminar: 

30th Annual European Symposium on Algorithms (ESA 2022)

Issue date: 

2022 
Date of publication: 

01.09.2022 