# Temporal Cliques Admit Sparse Spanners

arXiv: https://arxiv.org/abs/1810.00104 · HTML: https://mlsanity.com/paper/1810.00104/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2018.

## Built on by (most cited first, 1 of 1)

- [Temporal Network Creation Games](https://mlsanity.com/paper/2305.07494/) (2023)

## Abstract (arXiv)

Let G=(V,E) be an undirected graph on n vertices and λ:E→ 2^mathbbN a mapping that assigns to every edge a non-empty set of integer labels (times). Such a graph is em 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 citeKKK02 asked whether, given such a temporal graph, a em sparse subset of edges always exists whose labels suffice to preserve temporal connectivity -- a em temporal spanner. Axiotis and Fotakis citeAF16 answered negatively by exhibiting a family of Theta(n2)-dense temporal graphs which admit no temporal spanner of density o(n2). In this paper, we give the first positive answer as to the existence of o(n2)-sparse spanners in a dense class of temporal graphs, by showing (constructively) that if G is a complete graph, then one can always find a temporal spanner of density O(n log n).