<aside> 🌐
Outdated page — the Temporal Graph Wiki has moved. Read this page on temporalgraph.wiki.
</aside>
Temporal spanners are spanning temporal subgraphs that preserve specified communication guarantees while retaining only a subset of the available connections.
In static undirected graphs, every connected graph has a spanning tree with $n-1$ edges. Analogously, static directed graphs which are strongly connected contain a spanning aborescence (a directed spanning tree) that is an inclusion-minimal subgraph that is still strongly connected.
In contrast, a minimal temporally connected subgraph does not necessarily have a tree footprint Temporal connectivity need not survive the deletion of edges down to a tree: the order in which edges are available matters. The basic temporal-spanner problem therefore asks how much of a temporal graph must be retained to preserve temporal reachability.
Research studies the minimum possible size, the complexity of finding a minimum or sufficiently small spanner, the enumeration of spanners, and spanners with additional distance or robustness guarantees. A spanner is a feasible subgraph; being minimum or inclusion-minimal is a separate requirement.
The study of temporal spanners began with foundational observations on the difficulty of preserving temporal connectivity in sparse subgraphs.
(1972) Gossip Theory
(2000) Kempe, Kleinberg, and Kumar seminal paper Connectivity and Inference Problems for Temporal Networks
(2016) Axiotis and Fotakis On the Size and the Approximability of Minimum Temporally Connected Subgraphs
This ruled out the existence of subquadratic ($o(n^2)$-sparse) spanners in general graphs, which opened a line of research into identifying restricted classes of temporal graphs where sparse spanners are guaranteed: temporal cliques.
Subsequent directions include:
(2022) Casteigts, Raskin, Renken and Zamaraev Sharp Thresholds in Random Simple Temporal Graphs
(2022) Bilò, D’Angelo, Gualà, Leucci, Rossi Blackout-Tolerant Temporal Spanners
(2022) Bilò, D’Angelo, Gualà, Leucci, Rossi Sparse Temporal Spanners with Low Stretch
(2023) Bilò, Cohen, Friedrich, Gawendowicz, Klodt, Lenzner, Skretas Temporal Network Creation Games
Then some more results on temporal cliques.