{
  "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 $\\widetilde{\\mathcal{O}}(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/\\sqrt{\\ln n}}=n^{1+o(1)}$, thereby improving the previous best upper bound of $\\widetilde{\\mathcal{O}}(n^{3/2})$. We also show that a modified version of our algorithm computes temporal $3$-spanners of size $\\mathcal{O}(nL)$ when the lifetime is bounded by $L$, i.e., all time labels are in $\\{1,\\ldots,L\\}$, thus improving the previous bound of $\\mathcal{O}(2^Ln\\log 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\\geq 3$. Both algorithms rely on a new simple recursive decomposition that certifies temporal connectivity for a large collection of source-target pairs using only $\\mathcal{O}(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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.02851",
  "author_total": 5,
  "authors": [
    {
      "name": "Julia Baligacs"
    },
    {
      "name": "Davide Bilò"
    },
    {
      "name": "Václav Blažej"
    },
    {
      "name": "Maël Dumas"
    },
    {
      "name": "Anna Zych-Pawlewicz"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/1zsw2x786m3w4.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.02851",
  "fulltext_url": null,
  "id": "1zsw2x786m3w4",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.02851",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DM"
    ],
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "1703|Complexity and Algorithms in Graphs"
    ]
  ],
  "openalex": "W7207571283",
  "pdf_url": "https://arxiv.org/pdf/2609.02851",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-02",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/1zsw2x786m3w4.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:18:20Z",
      "native_id": "2609.02851",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.02851"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Almost Linear 3-Spanners of Temporal Cliques",
  "title_text": "Almost Linear 3-Spanners of Temporal Cliques",
  "type": "preprint",
  "updated_at": "2026-10-30T12:18:20Z",
  "url": "https://research.draconitic.com/paper/1zsw2x786m3w4",
  "venue": "arXiv",
  "versions": []
}