Temporal Cliques Admit Linear Spanners
2026-06-03 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study temporal graphs, where edges have times attached and connections must follow increasing time labels. They focus on finding smaller subgraphs, called spanners, that keep all these time-based connections intact. Before, the smallest known spanners for complete temporal graphs (cliques) were about n log n in size. The authors show that you only need about 7 times the number of vertices, n, which is a big improvement, and they provide a way to find these spanners efficiently.
Temporal graphTemporal connectivitySpannerTemporal cliqueNon-decreasing time pathGraph sparsificationPolynomial time algorithmUpper boundGraph theory
Authors
Julia Baligacs
Abstract
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.