Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs

Abstract

We introduce a generalized family of $\left(2\cdot \lfloor \frac{k}{2}\rfloor -1,2\cdot \lceil \frac{k}{2}\rceil \cdot W_1+\max \left\{0,2\cdot \left(\lceil \frac{k}{2}\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 $\hat{I}´\le O\left(3^{k^2}\right)$, our construction improves upon the seminal additive $+\tilde{O}\left(\hat{I}{´}^{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].