Almost Linear 3-Spanners of Temporal Cliques
Abstract
Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are traversed in nondecreasing order. A temporal α-spanner of a temporal graph with n vertices is a temporal subgraph that approximates the minimum-hop temporal distance between every pair of vertices within a factor of α. While general temporal graphs may not admit sparse temporal α-spanners for any value of α, temporal cliques are known to admit temporal (2k−1)-spanners of size 𝒪̃(kn1+1/k) for every positive integer k. We present a simple recursive algorithm that computes, for every temporal clique on n vertices, a temporal $3$-spanner of size n1+2/√(ln n)=n1+o(1), thereby improving the previous best upper bound of 𝒪̃(n3/2). We also show that a modified version of our algorithm computes temporal $3$-spanners of size 𝒪(nL) when the lifetime is bounded by L, i.e., all time labels are in {1,…,L}, thus improving the previous bound of 𝒪(2Lnlog n). Both results are particularly striking in light of the known lower bound of Ω(n2) on the size of temporal $2$-spanners, which already holds for temporal cliques of lifetime L≥ 3. Both algorithms rely on a new simple recursive decomposition that certifies temporal connectivity for a large collection of source-target pairs using only 𝒪(n) carefully selected edges and recursively processes only the remaining pairs. Besides yielding substantially improved upper bounds, this approach is significantly simpler than previous constructions.
Related
- Large Planar Point Sets Contain 4 Collinear Points or Almost 7-Cliques, and Related Results
- On canonicity of almost linear minimal orders
- Almost Symmetric Linear Arc Monadic Datalog and Transitive Tournaments
- Almost Linear Universal Point Sets for Planar Graphs
- Almost-linear Zarankiewicz bounds in $1$-semi-equational theories
BibTeX
@misc{baligacs2026almost,
title = {{Almost Linear 3-Spanners of Temporal Cliques}},
author = {Julia Baligacs and Davide Bilò and Václav Blažej and Maël Dumas and Anna Zych-Pawlewicz},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02851},
eprint = {2609.02851},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02851},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Almost Linear 3-Spanners of Temporal Cliques
AU - Julia Baligacs
AU - Davide Bilò
AU - Václav Blažej
AU - Maël Dumas
AU - Anna Zych-Pawlewicz
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.02851
UR - https://arxiv.org/abs/2609.02851
AB - Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are traversed in nondecreasing order. A temporal α-spanner of a temporal graph with n vertices is a temporal subgraph that approximates the minimum-hop temporal distance between every pair of vertices within a factor of α. While general temporal graphs may not admit sparse temporal α-spanners for any value of α, temporal cliques are known to admit temporal (2k−1)-spanners of size 𝒪̃(kn^1+1/k) for every positive integer k. We present a simple recursive algorithm that computes, for every temporal clique on n vertices, a temporal $3$-spanner of size n^1+2/√(ln n)=n^1+o(1), thereby improving the previous best upper bound of 𝒪̃(n^3/2). We also show that a modified version of our algorithm computes temporal $3$-spanners of size 𝒪(nL) when the lifetime is bounded by L, i.e., all time labels are in {1,…,L}, thus improving the previous bound of 𝒪(2^Lnlog n). Both results are particularly striking in light of the known lower bound of Ω(n^2) on the size of temporal $2$-spanners, which already holds for temporal cliques of lifetime L≥ 3. Both algorithms rely on a new simple recursive decomposition that certifies temporal connectivity for a large collection of source-target pairs using only 𝒪(n) carefully selected edges and recursively processes only the remaining pairs. Besides yielding substantially improved upper bounds, this approach is significantly simpler than previous constructions.
ER -