pipette
ENEnglish

Spanners and Hybrid Spanners with Nearly Tight Bounds

Shiri Chechik, Gur Lifshitz

Preprint con versión publicada

En palabras de los autores

For an -vertex undirected, unweighted graph and a positive integer , we present new spanner constructions with edges that achieve nearly optimal guarantees for all distances . Specifically, we construct a spanner with edges, ensuring that any pair at original distance at most satisfies . Equivalently, the multiplicative stretch for pairs at distance is . In particular, setting yields an -spanner with edges. For comparison, Ben-Levy and Parter (SODA'20) obtained, for every fixed and sufficiently large , an -spanner with edges. Our result improves the multiplicative stretch from to while keeping the additive term linear in , bringing us closer to the goal of -spanners. Furthermore, Ben-Levy and Parter obtained multiplicative stretch for distances , for every fixed , and an explicit bound of for . We achieve , which is whenever . Our second result is an improved construction of -hybrid spanners, which guarantee stretch for adjacent pairs and for non-adjacent pairs. Parter's original construction uses edges; we achieve the same guarantees with edges, removing the factor from the term. For every fixed , our edge bound is optimal up to a constant factor under Erd\H{o}s' girth conjecture.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 1 de octubre. arXiv. Preprint con versión publicada.

DOI: 10.1137/1.9781611978971.128

Versión publicada: Proceedings of SODA 2026, pp. 3511-3535

Comentario de los autores: A preliminary version appeared in SODA 2026