Temporal Cliques Admit Linear Spanners
Resolves a long-standing open problem in temporal graph theory by establishing linear-size spanners for temporal cliques, which is a fundamental result for the community studying temporal networks.
The paper proves that every temporal clique on n vertices admits a spanner of size at most 7n, improving the previous best bound of O(n log n), and shows such a spanner can be computed in polynomial time.
A temporal graph is a graph in which every edge carries a non-empty set of time labels, and it is temporally connected if for every two vertices $u$ and $v$, there exists a $u$-$v$-path with non-decreasing time labels. A spanner is a subset of its edges preserving temporal connectivity. Unlike static graphs, temporally connected graphs need not admit sparse spanners; nonetheless, minimizing spanner size is a central and widely studied problem. A particularly intriguing question is whether temporal cliques admit spanners of linear size. Despite considerable effort over the past years, the best known upper bound remained $O(n \log n)$. We finally resolve this question, proving that every temporal clique on $n$ vertices admits a spanner of size $7n$. Moreover, such a spanner can be computed in polynomial time.