Metraipolis › archive › dc_b95fdf59f01e

$(α, β)$ Spanners and Hybrid Spanners with Nearly Tight Bounds — arXiv:2609.39617

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.39617
License (as archived)
CC0-1.0
Archived
2026-10-07T15:17:11.160Z
SHA-256 of the archived text
ebc49a12af147372f961dd7f035a29467bfd13dbbee819aa1173635b87ccbf20
Stable URL of this page
https://metraipolis.com/documento/dc_b95fdf59f01e

How to cite

$(α, β)$ Spanners and Hybrid Spanners with Nearly Tight Bounds — arXiv:2609.39617 — arXiv (en), https://arxiv.org/abs/2609.39617 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b95fdf59f01e (Metraipolis archive dc_b95fdf59f01e, sha256 ebc49a12af147372f961dd7f035a29467bfd13dbbee819aa1173635b87ccbf20)
BibTeX
@misc{dcb95fdf59f01e,
  title = {$(α, β)$ Spanners and Hybrid Spanners with Nearly Tight Bounds — arXiv:2609.39617},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.39617},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b95fdf59f01e; sha256 ebc49a12af147372f961dd7f035a29467bfd13dbbee819aa1173635b87ccbf20},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.39617. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For an $n$-vertex undirected, unweighted graph $G=(V,E)$ and a positive integer $k$, we present new spanner constructions with $O_k(n^{1+1/k})$ edges that achieve nearly optimal guarantees for all distances $d\le k$. Specifically, we construct a spanner $H\subseteq G$ with $O(n^{1+1/k}+(k+d\log d)n)$ edges, ensuring that any pair at original distance at most $d$ satisfies $\mathrm{dist}_H(u,v)\le 2k+O(d\log d)$. Equivalently, the multiplicative stretch for pairs at distance $d$ is $2k/d+O(\log d)$. In particular, setting $d=k/\log k$ yields an $(O(\log k),O(k))$-spanner with $O(n^{1+1/k}+kn)$ edges. For comparison, Ben-Levy and Parter (SODA'20) obtained, for every fixed $\varepsilon>0$ and sufficiently large $k$, an $(O(k^\varepsilon),O_\varepsilon(k))$-spanner with $O_{\varepsilon,k}(n^{1+1/k})$ edges. Our result improves the multiplicative stretch from $O(k^\varepsilon)$ to $O(\log k)$ while keeping the additive term linear in $k$, bringing us closer to the goal of $(O(1),O(k))$-spanners. Furthermore, Ben-Levy and Parter obtained multiplicative stretch $O_\varepsilon(k/d)$ for distances $d\le k^{1-\varepsilon}$, for every fixed $\varepsilon>0$, and an explicit bound of $7k/d$ for $d\le\sqrt{k}/2$. We achieve $2k/d+O(\log d)$, which is $(2+o(1))k/d$ whenever $d=o(k/\log k)$. Our second result is an improved construction of $k$-hybrid spanners, which guarantee stretch $2k-1$ for adjacent pairs and $k$ for non-adjacent pairs. Parter's original construction uses $O(k^2 n^{1+1/k})$ edges; we achieve the same guarantees with $O(n^{1+1/k}+kn)$ edges, removing the $k^2$ factor from the $n^{1+1/k}$ term. For every fixed $k$, our edge bound is optimal up to a constant factor under Erdős' girth conjecture.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.39617 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:50:37.648Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).