Sparse Temporal Spanners with Low Stretch

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



PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.19.pdf
  • Filesize: 1.11 MB
  • 16 pages

Document Identifiers

Author Details

Davide Bilò
  • Department of Information Engineering, Computer Science and Mathematics, University of L'Aquila, Italy
Gianlorenzo D'Angelo
  • Gran Sasso Science Institute, L'Aquila, Italy
Luciano Gualà
  • Department of Enterprise Engineering, University of Rome "Tor Vergata", Italy
Stefano Leucci
  • Department of Information Engineering, Computer Science and Mathematics, University of L'Aquila, Italy
Mirko Rossi
  • Gran Sasso Science Institute, L'Aquila, Italy

Cite AsGet BibTex

Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci, and Mirko Rossi. Sparse Temporal Spanners with Low Stretch. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.19

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
Keywords
  • temporal spanners
  • temporal graphs
  • graph sparsification
  • approximate distances

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen G. Kobourov, and Richard Spence. Graph spanners: A tutorial review. Comput. Sci. Rev., 37:100253, 2020. URL: https://doi.org/10.1016/j.cosrev.2020.100253.
  2. Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios, and Paul G. Spirakis. The complexity of optimal design of temporally connected graphs. Theory Comput. Syst., 61(3):907-944, 2017. URL: https://doi.org/10.1007/s00224-017-9757-x.
  3. Ingo Althöfer, Gautam Das, David P. Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discret. Comput. Geom., 9:81-100, 1993. URL: https://doi.org/10.1007/BF02189308.
  4. Kyriakos Axiotis and Dimitris Fotakis. On the size and the approximability of minimum temporally connected subgraphs. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 149:1-149:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.149.
  5. Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms, 30(4):532-563, 2007. URL: https://doi.org/10.1002/rsa.20130.
  6. Davide Bilò, Fabrizio Grandoni, Luciano Gualà, Stefano Leucci, and Guido Proietti. Improved purely additive fault-tolerant spanners. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 167-178. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_15.
  7. Arnaud Casteigts, Joseph G. Peters, and Jason Schoeters. Temporal cliques admit sparse spanners. J. Comput. Syst. Sci., 121:1-17, 2021. URL: https://doi.org/10.1016/j.jcss.2021.04.004.
  8. Arnaud Casteigts, Michael Raskin, Malte Renken, and Viktor Zamaraev. Sharp thresholds in random simple temporal graphs. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 2022. Full version at URL: https://arxiv.org/abs/2011.03738.
  9. Petter Holme. Temporal networks. In Reda Alhajj and Jon G. Rokne, editors, Encyclopedia of Social Network Analysis and Mining, 2nd Edition. Springer, 2018. URL: https://doi.org/10.1007/978-1-4939-7131-2_42.
  10. Silu Huang, Ada Wai-Chee Fu, and Ruifeng Liu. Minimum spanning trees in temporal graphs. In Timos K. Sellis, Susan B. Davidson, and Zachary G. Ives, editors, Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015, pages 419-430. ACM, 2015. URL: https://doi.org/10.1145/2723372.2723717.
  11. David Kempe, Jon M. Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci., 64(4):820-842, 2002. URL: https://doi.org/10.1006/jcss.2002.1829.
  12. George B. Mertzios, Othon Michail, and Paul G. Spirakis. Temporal network optimization subject to connectivity constraints. Algorithmica, 81(4):1416-1449, 2019. URL: https://doi.org/10.1007/s00453-018-0478-6.
  13. Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi Lu, and Yanyan Xu. Path problems in temporal graphs. Proc. VLDB Endow., 7(9):721-732, 2014. URL: https://doi.org/10.14778/2732939.2732945.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail