License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.19
URN: urn:nbn:de:0030-drops-169575
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16957/
Go to the corresponding LIPIcs Volume Portal

Bilò, Davide ; D'Angelo, Gianlorenzo ; Gualà, Luciano ; Leucci, Stefano ; Rossi, Mirko

Sparse Temporal Spanners with Low Stretch

pdf-format:
LIPIcs-ESA-2022-19.pdf (1 MB)

Abstract

A temporal graph is an undirected graph G = (V,E) along with a function λ : E → ℕ^+ 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 Õ(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 connectivity-preserving 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 single-source 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 time-labels, affects the trade-off 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:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16957},
  URN =		{urn:nbn:de:0030-drops-169575},
  doi =		{10.4230/LIPIcs.ESA.2022.19},
  annote =	{Keywords: temporal spanners, temporal graphs, graph sparsification, approximate distances}
}

Keywords: temporal spanners, temporal graphs, graph sparsification, approximate distances
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI