Temporal cliques admit sparse spanners
Arnaud Casteigts, Joseph G. Peters, Jason Schoeters · Journal of Computer and System Sciences · 2021
Let G=(V,E) be an undirected graph on n vertices and λ:E→2N a mapping that assigns to every edge a non-empty set of integer labels (discrete times when the edge is present). Such a labelled graph G=(G,λ) is 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 [17] asked whether, given such a temporally connected graph, a sparse subset of edges always exists whose labels suffice to preserve temporal connectivity – a temporal spanner. Axiotis and Fotakis [5] answered negatively by exhibiting a family of Θ(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 with O(nlogn) edges.