Temporal Cliques Admit Sparse Spanners

Authors Arnaud Casteigts , Joseph G. Peters , Jason Schoeters



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.134.pdf
  • Filesize: 478 kB
  • 14 pages

Document Identifiers

Author Details

Arnaud Casteigts
  • LaBRI, Université de Bordeaux, CNRS, Bordeaux INP, France
Joseph G. Peters
  • School of Computing Science, Simon Fraser University, Canada
Jason Schoeters
  • LaBRI, Université de Bordeaux, CNRS, Bordeaux INP, France

Acknowledgements

We thank Cyril Gavoille for advice on the presentation of these results.

Cite AsGet BibTex

Arnaud Casteigts, Joseph G. Peters, and Jason Schoeters. Temporal Cliques Admit Sparse Spanners. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 134:1-134:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.134

Abstract

Let G=(V,E) be an undirected graph on n vertices and lambda:E -> 2^{N} a mapping that assigns to every edge a non-empty set of positive integer labels. These labels can be seen as discrete times when the edge is present. Such a labeled graph {G}=(G,lambda) is said to be temporally connected if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar (STOC 2000) asked whether, given such a temporal graph, a sparse subset of edges can always be found whose labels suffice to preserve temporal connectivity - a temporal spanner. Axiotis and Fotakis (ICALP 2016) answered negatively by exhibiting a family of Theta(n^2)-dense temporal graphs which admit no temporal spanner of density o(n^2). The natural question is then whether sparse temporal spanners always exist in some classes of dense graphs. In this paper, we answer this question affirmatively, by showing that if the underlying graph G is a complete graph, then one can always find temporal spanners of density O(n log n). The best known result for complete graphs so far was that spanners of density binom{n}{2}- floor[n/4] = O(n^2) always exist. Our result is the first positive answer as to the existence of o(n^2) sparse spanners in adversarial instances of temporal graphs since the original question by Kempe et al., focusing here on complete graphs. The proofs are constructive and directly adaptable as an algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Dynamic networks
  • Temporal graphs
  • Temporal connectivity
  • Sparse spanners

Metrics

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

References

  1. Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios, and Paul G. Spirakis. The complexity of optimal design of temporally connected graphs. Theory of Computing Systems, 61(3):907-944, 2017. Google Scholar
  2. Sunil Arya, David M Mount, and Michiel Smid. Dynamic algorithms for geometric spanners of small diameter: Randomized solutions. Computational Geometry, 13(2):91-107, 1999. Google Scholar
  3. B. Awerbuch and S. Even. Efficient and reliable broadcast is achievable in an eventually connected network. In Proceedings of 3rd Symposium on Principles of Distributed Computing (PODC), pages 278-281, 1984. Google Scholar
  4. Kyriakos Axiotis and Dimitris Fotakis. On the Size and the Approximability of Minimum Temporally Connected Subgraphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 149:1-149:14, 2016. Google Scholar
  5. Bin-Minh Bui-Xuan, Afonso Ferreira, and Aubin Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. International Journal of Foundations of Computer Science, 14(2):267-285, 2003. Google Scholar
  6. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387-408, 2012. Google Scholar
  7. Arnaud Casteigts, Joseph G Peters, and Jason Schoeters. Temporal Cliques admit Sparse Spanners. arXiv preprint, 2019. URL: http://arxiv.org/abs/1810.00104.
  8. Paul Chew. There is a planar graph almost as good as the complete graph. In Proceedings of 2nd Symposium on Computational Geometry, pages 169-177, 1986. Google Scholar
  9. Michael Elkin. A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. In Proceedings of 26th ACM Symposium on Principles of Distributed Computing, pages 185-194, 2007. Google Scholar
  10. Lee-Ad Gottlieb and Liam Roditty. Improved algorithms for fully dynamic geometric spanners and geometric routing. In 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 591-600, 2008. Google Scholar
  11. Petter Holme and Jari Saramäki. Temporal Networks. Springer, 2013. Google Scholar
  12. D. Kempe, J. Kleinberg, and A. Kumar. Connectivity and inference problems for temporal networks. In 32nd ACM Symposium on Theory of Computing (STOC), pages 504-513, 2000. Google Scholar
  13. David Kempe, Jon Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences, 64(4):820-842, 2002. Google Scholar
  14. Othon Michail and Paul G Spirakis. Elements of the theory of dynamic networks. Communications of the ACM, 61(2):72-72, 2018. Google Scholar
  15. Giri Narasimhan and Michiel Smid. Geometric Spanner Networks. Cambridge Univ. Press, 2007. Google Scholar
  16. Ariel Orda and Raphael Rom. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. Journal of the ACM (JACM), 37(3):607-625, 1990. Google Scholar
  17. David Peleg and Alejandro A Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. Google Scholar
  18. Tiphaine Viard, Matthieu Latapy, and Clémence Magnien. Computing maximal cliques in link streams. Theoretical Computer Science, 609:245-252, 2016. Google Scholar
  19. Philipp Zschoche, Till Fluschnik, Hendrik Molter, and Rolf Niedermeier. The Complexity of Finding Small Separators in Temporal Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 45:1-45:17, 2018. Google Scholar
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