# Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs

Preprint · Liam Roditty, Ariel Sapir

- Archive id: arxiv:2604.26831
- Published: 2026-04-29
- arXiv: https://arxiv.org/abs/2604.26831
- Source URL: https://arxiv.org/abs/2604.26831
- PDF: https://arxiv.org/pdf/2604.26831
- Provenance: arxiv

## Abstract

We introduce a generalized family of $\\left( 2\\cdot \\left\\lfloor \\frac{k}{2} \\right\\rfloor-1, 2\\cdot \\left\\lceil \\frac{k}{2} \\right\\rceil \\cdot W\_{1} +\\max\\left\\{0,2\\cdot\\left(\\left\\lceil\\frac{k}{2}\\right\\rceil-2\\right)\\right\\}\\cdot W\_{2} \\right)$-emulators with $\\tilde O \\left(n^{1+\\frac{1}{k}}\\right)$ edges, for any $k\\in\\mathbb{N}$, where $W\_{i}$ is the $i$th heaviest edge on a shortest path between two vertices. Our construction generalizes the $+2W\_{1}$-spanner of size $\\tilde O\\left(n^{\\frac{3}{2}}\\right)$ and the $+4W\_{1}$-emulator of size $\\tilde O \\left(n^{\\frac{4}{3}}\\right)$, both by Elkin, Gitlitz and Neiman \[DISC'21 and DICO'23\]. When $k$ is even, these are $\\left(k-1,k\\cdot W\_{1} + \\left(k-4\\right)\\cdot W\_{2}\\right)$-emulators and when $k$ is odd, these are $\\left(k-2,\\left(k+1\\right)\\cdot W\_{1} + \\left(k-3\\right) \\cdot W\_{2}\\right)$-emulators. Our framework not only expands known constructions for weighted graphs but also yields an improved stretch over state of the art emulators and spanners for unweighted graphs within a specific distance regime. In particular, for all vertex pairs separated by a distance of $δ\\leq O\\left(3^{k^{2}}\\right)$, our construction improves upon the seminal additive $+\\tilde O\\left(δ^{1-\\frac{1}{k}}\\right)$-emulator of size $\\tilde O\\left(n^{1+\\frac{1}{2^{k+1}-1}}\\right)$ by Thorup and Zwick \[SODA'06\].

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.