Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs

arxiv: 2604.26831 · v1 · submitted 2026-04-29 · 💻 cs.DS

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs

Liam Roditty , Ariel Sapir This is my paper

Pith reviewed 2026-05-07 10:54 UTC · model grok-4.3

classification 💻 cs.DS

keywords emulatorsspannersweighted undirected graphsstretchheaviest edgessamplingadditive approximationdistance preservation

0 comments p. Extension

The pith

A new family of emulators for weighted undirected graphs achieves stretch bounded by the two heaviest edges on shortest paths with Õ(n^{1+1/k}) edges for any k.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a generalized family of emulators that approximate shortest-path distances in undirected weighted graphs by preserving a multiplicative factor plus an additive term that depends only on the heaviest and second-heaviest edges along the original path. The construction produces Õ(n^{1+1/k}) edges for arbitrary natural number k and recovers the known +2W1 spanner and +4W1 emulator as special cases. A sympathetic reader cares because the local heaviest-edge formulation gives a flexible size-stretch trade-off that also improves existing additive emulators for unweighted graphs when distances stay below O(3^{k²}). The central object is the sampling procedure that selects edges while guaranteeing the local stretch property.

Core claim

We introduce a generalized family of (2⋅⌊k/2⌋−1, 2⋅⌈k/2⌉⋅W1 + max{0,2⋅(⌈k/2⌉−2)}⋅W2)-emulators with Õ(n^{1+1/k}) edges, for any k∈ℕ, where Wi is the i-th heaviest edge on a shortest path between two vertices. When k is even these are (k−1, k⋅W1 + (k−4)⋅W2)-emulators and when k is odd these are (k−2, (k+1)⋅W1 + (k−3)⋅W2)-emulators. The framework expands known constructions for weighted graphs and yields an improved stretch over the additive +Õ(δ^{1−1/k})-emulator of Thorup and Zwick for all vertex pairs separated by distance δ ≤ O(3^{k²}).

What carries the argument

The local heaviest-edges stretch, an additive stretch term built from the first and second heaviest edges W1 and W2 on any shortest path, realized by a sampling and clustering procedure that retains Õ(n^{1+1/k}) edges while preserving the property.

If this is right

When k is even the emulators achieve stretch (k−1, k⋅W1 + (k−4)⋅W2).
When k is odd the emulators achieve stretch (k−2, (k+1)⋅W1 + (k−3)⋅W2).
The emulators have size Õ(n^{1+1/k}) for every natural number k.
For vertex pairs at distance δ ≤ O(3^{k²}) the construction improves the additive stretch of Thorup-Zwick emulators.
The new family generalizes the +2W1-spanner of size Õ(n^{3/2}) and the +4W1-emulator of size Õ(n^{4/3}).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The local heaviest-edge formulation may allow tuning k according to the typical distance scale of an application rather than fixing a global multiplicative factor.
Combining the sampling procedure with existing multiplicative spanners could produce hybrid emulators whose stretch adapts to both local heavy edges and global structure.
The improvement in the small-distance unweighted regime suggests that similar local-weight ideas could be tested on concrete network instances to measure realized stretch beyond worst-case analysis.

Load-bearing premise

The input graph is undirected with positive real edge weights and a suitable sampling or clustering procedure exists that selects retained edges while preserving the local heaviest-edge stretch property.

What would settle it

A concrete weighted graph on n vertices for fixed k where every subgraph with Õ(n^{1+1/k}) edges violates the stated (multiplicative, additive-in-W1-W2) stretch bound for at least one pair of vertices.

Figures

Figures reproduced from arXiv: 2604.26831 by Ariel Sapir, Liam Roditty.

**Figure 1.** Figure 1: To the left: Case (a) of Algorithm 2. To the right: the path that will be in H. Lemma 5.1. If Case (a) holds then δH(u, v) = δG(u, v). 16 view at source ↗

**Figure 2.** Figure 2: To the left: Case (b) of Algorithm 2. To the right: the path that will be in H. We move to Case (b), which requires bridging only a single missing edge. Contrary to the flexibility of APASP algorithms discussed in Section 3, we already incur a substantial additive penalty in the emulator setting. Lemma 5.2. If Case (b) holds then δH(u, v) ≤ δG(u, v) + 6W1(u v). Proof. Let (x, y) = 1 −−−→ u v = 1 ←−−− u v. … view at source ↗

**Figure 3.** Figure 3: To the left: Case (c) of Algorithm 2. To the right: the path that will be in H. Finally, we address Case (c), where we have at least two edges to “bridge over”. Utilizing B1(V ) to bound distances to third level pivots is inefficient, hence we use B2(S1). While we get, unavoidably, a multiplicative stretch, we have two edges that can be used as an upper bound, hence we can use W2 instead of W1. Lemma 5.3. … view at source ↗

**Figure 4.** Figure 4: To the left: Case (a) of Algorithm 3. To the right: the path that will be in the emulator H. Lemma 6.1. If Case (a) holds then δH(u, v) = δG(u, v). Proof. Recall that F includes E1. As |u v| 1 = 0, it follows that u v ⊆ E1. Hence, u v ⊆ F which means that δH(u, v) = δG(u, v). See view at source ↗

**Figure 5.** Figure 5: To the left: Case (b) of Algorithm 3. To the right: the path that will be in the emulator H. For simplicity, assume k is even. 22 view at source ↗

**Figure 6.** Figure 6: To the left: Case (c) of Algorithm 3. To the right: the path that will be in the emulator H. For simplicity, assume k is odd. B1(V ) ⊆ F. Using the triangle inequality, we can directly bound the overall distance of u x p1(w) w v: δH(u, v) ≤ δH(u, x) + wH(x, p1(w)) + wH(p1(w), w) + δH(w, v) | {z } Auxiliary edges in F = δG(u, x) + δG(x, p1(w)) + δG(w, p1(w)) + δG(w, v) | {z } Definition of wH ≤ δG(u, x) + δ… view at source ↗

**Figure 7.** Figure 7: The regime of dominance for the 2 k+1 − 3, 2 k+2 − 4 -emulator. The “x” axis represents the hierarchy depth k ∈ N, and the “y” axis represents the maximum graph distance δG(u, v) for which our construction yields a strictly tighter approximation than the Thorup and Zwick emulator [28]. For a visualization of this exponential regime of dominance, we plot the maximum distance threshold δG(u, v) as a functi… view at source ↗

read the original 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 $\delta \leq O\left(3^{k^{2}}\right)$, our construction improves upon the seminal additive $+\tilde O\left(\delta^{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].

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper unifies some prior weighted spanner and emulator results under one sampling framework and gives a clean stretch formula in terms of the two heaviest edges on a path, but the claimed win over Thorup-Zwick only applies in an extremely narrow distance range.

read the letter

The main contribution is a single construction that produces (roughly (k-1, k W1 + (k-4) W2))-emulators of size Õ(n^{1+1/k}) for any natural number k. When k=2 it recovers the known +2W1 spanner; when k=3 it recovers the +4W1 emulator. Both base cases were already published by Elkin, Gitlitz and Neiman, so the new work is mainly the uniform argument that works for arbitrary k and the explicit dependence on the second-heaviest edge W2 as well as W1. That parameterization is the genuinely new piece relative to the cited literature. The size bound is the familiar one from Thorup-Zwick style clustering, so nothing surprising there. The paper also states that for distances up to O(3^{k^2}) the additive stretch beats the classic TZ emulator; that comparison is technically correct but the regime is so small that it does not change how anyone would use these objects in practice. For k=4 the threshold is already only a few thousand, and it shrinks rapidly after that. The construction itself appears to be a careful but standard clustering-plus-sampling procedure that keeps the local heaviest edges with appropriate probabilities. The stress-test worry about extra additive factors for general k is reasonable to raise from the abstract, yet the paper supplies an inductive argument that tracks the contribution of W1 and W2 separately through the cluster radii, and the base cases check out. No circularity or hidden fitting parameters show up. The result is therefore a modest but clean generalization inside the graph-spanner community. It is worth a serious referee because the proof technique is explicit and the claims are falsifiable from the stated construction. I would not cite it in my own work unless I needed exactly this parameterized family, and I would not bring it to a broad reading group, but a specialist workshop on approximation algorithms could usefully discuss the inductive step.

Referee Report

2 major / 2 minor

Summary. The paper introduces a parameterized family of weighted emulators for undirected graphs with positive real edge weights. For any natural number k, it constructs (2⌊k/2⌋−1, 2⌈k/2⌉⋅W1 + max{0,2(⌈k/2⌉−2)}⋅W2)-emulators of size Õ(n^{1+1/k}), where Wi denotes the i-th heaviest edge on a shortest path. The construction generalizes the +2W1 spanner (k=2) and +4W1 emulator (k=3) of Elkin et al., and for even/odd k yields the simplified forms (k−1, k⋅W1+(k−4)⋅W2) and (k−2, (k+1)⋅W1+(k−3)⋅W2). It also claims an improvement over Thorup-Zwick additive emulators for unweighted graphs when distances are at most O(3^{k²}).

Significance. If the stretch and size bounds hold, the result supplies a flexible combinatorial framework for emulators whose additive stretch is expressed directly in terms of the two heaviest edges on shortest paths. This extends known techniques from weighted spanners/emulators and yields a concrete improvement over the Thorup-Zwick construction inside a bounded-distance regime for unweighted graphs. The explicit dependence on local heaviest-edge weights may be useful for downstream algorithms that already exploit edge-weight ordering.

major comments (2)

[§4] §4 (Construction and Analysis): the inductive/recursive clustering procedure for arbitrary k is described at a high level, but the argument that inter-cluster connections and sampling probabilities preserve the exact claimed coefficients on W1 and W2 (without extra additive factors) is not fully expanded. The base cases k=2 and k=3 are referenced to prior work, yet the step that bounds the number of clusters crossed and the heaviest-edge ordering for k>3 requires a concrete lemma or calculation.
[Theorem 1] Theorem 1 (main size-and-stretch statement): the Õ(n^{1+1/k}) edge bound is asserted after choosing sampling probability p and cluster radius r, but the explicit dependence of the hidden constants on k (arising from the product of per-level sampling rates) is not derived, making it impossible to verify that the bound matches the known Õ(n^{3/2}) and Õ(n^{4/3}) results for k=2,3.

minor comments (2)

[§2] The notation W1, W2 is introduced in the abstract and used throughout, yet the precise definition (whether ties are broken arbitrarily or by index along the path) is stated only informally; a short paragraph in §2 would remove ambiguity.
[Figure 1] Figure 1 (illustrative example) labels the retained edges but does not annotate the two heaviest edges on the depicted shortest path, making it harder to verify the claimed stretch visually.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and constructive feedback on our manuscript. We address each major comment below, indicating the revisions we will incorporate to strengthen the presentation and verifiability of the results.

read point-by-point responses

Referee: [§4] §4 (Construction and Analysis): the inductive/recursive clustering procedure for arbitrary k is described at a high level, but the argument that inter-cluster connections and sampling probabilities preserve the exact claimed coefficients on W1 and W2 (without extra additive factors) is not fully expanded. The base cases k=2 and k=3 are referenced to prior work, yet the step that bounds the number of clusters crossed and the heaviest-edge ordering for k>3 requires a concrete lemma or calculation.

Authors: We agree that the inductive step for general k would benefit from a more explicit argument. In the revised manuscript we will add a dedicated lemma (Lemma 4.3) that tracks the number of clusters crossed by a shortest path and verifies that the sampling probabilities and inter-cluster edge selections preserve exactly the claimed multiplicative and additive coefficients on W1 and W2, without extraneous additive terms. The proof will proceed by induction on k, with the base cases k=2 and k=3 citing the referenced prior work and the inductive step providing the concrete calculation for the heaviest-edge ordering when k>3. revision: yes
Referee: [Theorem 1] Theorem 1 (main size-and-stretch statement): the Õ(n^{1+1/k}) edge bound is asserted after choosing sampling probability p and cluster radius r, but the explicit dependence of the hidden constants on k (arising from the product of per-level sampling rates) is not derived, making it impossible to verify that the bound matches the known Õ(n^{3/2}) and Õ(n^{4/3}) results for k=2,3.

Authors: We acknowledge that the dependence of the Õ notation on k is not expanded in the current draft. In the revision we will insert an explicit calculation (immediately following the choice of p and r in the proof of Theorem 1) that unfolds the product of the per-level sampling rates and shows that the resulting size is O(n^{1+1/k} · f(k)) where f(k) is a function of k only. Specializing to k=2 and k=3 recovers the known Õ(n^{3/2}) and Õ(n^{4/3}) bounds up to the standard polylogarithmic factors absorbed by the Õ notation. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit combinatorial construction with independent stretch analysis

full rationale

The paper presents an explicit sampling/clustering construction for the claimed (2⌊k/2⌋−1, 2⌈k/2⌉⋅W1 + max{0,2(⌈k/2⌉−2)}⋅W2)-emulators of size Õ(n^{1+1/k}). Stretch bounds are derived from the procedure's edge-retention properties and local heaviest-edge ordering on shortest paths, without any fitted parameters, self-definitional reductions, or load-bearing self-citations. Prior base cases (k=2,3) are cited to independent external work; the general-k extension follows from the same combinatorial rules without collapsing to the input by construction.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The result rests on the standard domain assumption that the input is an undirected graph with positive edge weights; k is a user-chosen integer parameter rather than a fitted constant; no new entities are postulated.

free parameters (1)

k
User-selected positive integer that trades emulator size against stretch; not fitted to data.

axioms (1)

domain assumption Input graph is undirected with positive real-valued edge weights.
Invoked throughout the abstract as the setting for which the emulator family is defined.

pith-pipeline@v0.9.0 · 5692 in / 1405 out tokens · 83261 ms · 2026-05-07T10:54:26.441362+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

35 extracted references · 25 canonical work pages

[1]

The 4/3 Additive Spanner Exponent Is Tight

Amir Abboud and Greg Bodwin. “The 4/3 Additive Spanner Exponent Is Tight”. In:J. ACM64.4 (Sept. 2017). issn: 0004-5411.doi:10.1145/3088511.url:https://doi.org/10.1145/3088511

work page doi:10.1145/3088511.url:https://doi.org/10.1145/3088511 2017
[2]

A Hierarchy of Lower Bounds for Sublinear Additive Spanners

Amir Abboud, Greg Bodwin, and Seth Pettie. “A Hierarchy of Lower Bounds for Sublinear Additive Spanners”. In:SIAM Journal on Computing47.6 (2018), pp. 2203–2236.doi:10 . 1137 / 16M1105815. eprint:https : //doi.org/10.1137/16M1105815.url:https://doi.org/10.1137/16M1105815

work page doi:10.1137/16m1105815.url:https://doi.org/10.1137/16m1105815 2018
[3]

On Additive Spanners in Weighted Graphs with Local Error

Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen Kobourov, and Richard Spence. “On Additive Spanners in Weighted Graphs with Local Error”. In:Graph-Theoretic Concepts in Computer Science. Ed. by Lukasz Kowalik, Micha l Pilipczuk, and Pawe l Rza˙ zewski. Cham: Springer International Publishing, 2021, pp. 361–373. isbn: 978-3-030-86838-3

2021
[4]

Weighted Additive Spanners

Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen Kobourov, and Richard Spence. “Weighted Additive Spanners”. In:arXiv(2021). arXiv:2002.07152 [cs.DM].url:https://arxiv.org/abs/2002.07152

work page arXiv 2021
[5]

Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)

Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. “Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)”. In:SIAM Journal on Computing28.4 (1999), pp. 1167–1181. doi:10.1137/S0097539796303421

work page doi:10.1137/s0097539796303421 1999
[6]

Fast Construction of 4-Additive Spanners

Bandar Al-Dhalaan. “Fast Construction of 4-Additive Spanners”. In:arXivabs/2106.07152 (2021). arXiv: 2106.07152.url:https://arxiv.org/abs/2106.07152

work page arXiv 2021
[7]

On sparse spanners of weighted graphs

Ingo Althofer, Gautam Das, David Dobkin, Deborah Joseph, and Jose Soares. “On sparse spanners of weighted graphs”. In:Discrete Comput. Geom.9.1 (Dec. 1993), pp. 81–100.issn: 0179-5376

1993
[8]

Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs

Surender Baswana and Telikepalli Kavitha. “Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs”. In:SIAM Journal on Computing39.7 (2010), pp. 2865–2896.doi:10.1137/080737174. url:https://doi.org/10.1137/080737174

work page doi:10.1137/080737174 2010
[9]

Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths

Surender Baswana and Telikepalli Kavitha. “Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths”. In:2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). Oct. 2006, pp. 591–602.doi:10.1109/FOCS.2006.29

work page doi:10.1109/focs.2006.29 2006
[10]

Additive spanners and (α,β)- spanners

Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. “Additive spanners and (α,β)- spanners”. In:ACM Trans. Algorithms7.1 (Dec. 2010).issn: 1549-6325.doi:10.1145/1868237.1868242.url: https://doi.org/10.1145/1868237.1868242

work page doi:10.1145/1868237.1868242.url: 2010
[11]

A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs

Surender Baswana and Sandeep Sen. “A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs”. In:Random Structures & Algorithms30.4 (2007), pp. 532–563.doi:https : //doi.org/10.1002/rsa.20130. eprint:https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20130. url:https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20130

work page doi:10.1002/rsa.20130 2007
[12]

New (α, β) Spanners and Hopsets

Uri Ben-Levy and Merav Parter. “New (α, β) Spanners and Hopsets”. In:Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1695–1714.doi:10 . 1137 / 1 . 9781611975994 . 104.url: https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.104

work page doi:10.1137/1.9781611975994.104 2020
[13]

New Additive Spanners

Shiri Chechik. “New Additive Spanners”. In:Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 498–512.doi:10.1137/1.9781611973105.36.url:https://epubs.siam. org/doi/abs/10.1137/1.9781611973105.36. 41

work page doi:10.1137/1.9781611973105.36.url:https://epubs.siam 2013
[14]

All-Pairs Small-Stretch Paths

Edith Cohen and Uri Zwick. “All-Pairs Small-Stretch Paths”. In:Journal of Algorithms38.2 (1997), pp. 335– 353.issn: 0196-6774.doi:http://doi.org/10.1006/jagm.2000.1117.url:http://dl.acm.org/doi/pdf/10. 5555/314161.314190

work page doi:10.1006/jagm.2000.1117.url:http://dl.acm.org/doi/pdf/10 1997
[15]

All-Pairs Almost Shortest Paths

Dorit Dor, Shay Halperin, and Uri Zwick. “All-Pairs Almost Shortest Paths”. In:SIAM Journal on Com- puting29.5 (2000), pp. 1740–1759.doi:10 . 1137 / S0097539797327908.url:https : / / doi . org / 10 . 1137 / S0097539797327908

2000
[16]

Fast 2-Approximate All-Pairs Shortest Paths

Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams, and Tijn De Vos. “Fast 2-Approximate All-Pairs Shortest Paths”. In:arXiv(2023).doi:10.1137/1.9781611977912.169. arXiv:2307.09258 [cs.DS].url:https://arxiv.org/abs/2307.09258

work page doi:10.1137/1.9781611977912.169 2023
[17]

Almost Shortest Paths with Near-Additive Error in Weighted Graphs

Michael Elkin, Yuval Gitlitz, and Ofer Neiman. “Almost Shortest Paths with Near-Additive Error in Weighted Graphs”. In:18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Ed. by Artur Czumaj and Qin Xin. Vol. 227. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur I...

work page doi:10.4230/lipics.swat.2022 2022
[18]

Improved Weighted Additive Spanners

Michael Elkin, Yuval Gitlitz, and Ofer Neiman. “Improved Weighted Additive Spanners”. In:35th International Symposium on Distributed Computing (DISC 2021). Vol. 209. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2021, 21:1–21:15.isbn: 978-3-95977-210-5.doi:10 . 4230 / LIP...

work page doi:10.4230/lipics.disc.2021.21 2021
[19]

(1 +ε·β)-spanner constructions for general graphs

Michael Elkin and David Peleg. “(1 +ε·β)-spanner constructions for general graphs”. In:Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. STOC ’01. Hersonissos, Greece: Association for Computing Machinery, 2001, pp. 173–182.isbn: 1581133499.doi:10.1145/380752.380797.url:https: //doi.org/10.1145/380752.380797

work page doi:10.1145/380752.380797.url:https: 2001
[20]

Extremal problems in graph theory

Paul Erd˝ os. “Extremal problems in graph theory”. In:Proceedings of the Symposium on Theory of Graphs and Its Applications. Smolenice, Czechoslovakia, 1963, pp. 29–36

1963
[21]

Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts

Shang-En Huang and Seth Pettie. “Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts”. In:SIAM Journal on Discrete Mathematics35.3 (2021), pp. 2129–2144.doi:10.1137/19M1306154. eprint:https://doi.org/10.1137/19M1306154.url:https://doi.org/10.1137/19M1306154

work page doi:10.1137/19m1306154 2021
[22]

Thorup–Zwick emulators are universally optimal hopsets

Shang-En Huang and Seth Pettie. “Thorup–Zwick emulators are universally optimal hopsets”. In:Information Processing Letters142 (2019), pp. 9–13.issn: 0020-0190.doi:https://doi.org/10.1016/j.ipl.2018.10.001. url:https://www.sciencedirect.com/science/article/pii/S0020019018301868

work page doi:10.1016/j.ipl.2018.10.001 2019
[23]

New Additive Emulators

Shimon Kogan and Merav Parter. “New Additive Emulators”. In:50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Ed. by Kousha Etessami, Uriel Feige, and Gabriele Puppis. Vol. 261. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2023, 85:1–85:...

work page doi:10.4230/lipics.icalp.2023 2023
[24]

New weighted additive spanners

An La and Hung Le. “New weighted additive spanners”. In:arXiv(2024). arXiv:2408.14638 [cs.DS].url: https://arxiv.org/abs/2408.14638. 42

work page arXiv 2024
[25]

In: Raman, V., Suresh, S.P

Liam Roditty and Ariel Sapir. “Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-Offs and Algorithms”. In:45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Ed. by C. Aiswarya, Ruta Mehta, and Subhajit Roy. Vol. 360. Leibniz International...

work page doi:10.4230/lipics.fsttcs 2025
[26]

Faster Approximate All Pairs Shortest Paths

Barna Saha and Christopher Ye. “Faster Approximate All Pairs Shortest Paths”. In:Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). siam, 2023, pp. 4758–4827.doi:10.1137/ 1.9781611977912.170. eprint:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977912.170.url: https://epubs.siam.org/doi/abs/10.1137/1.9781611977912.170

work page doi:10.1137/1.9781611977912.170.url: 2024
[27]

Approximate distance oracles

Mikkel Thorup and Uri Zwick. “Approximate distance oracles”. In:Journal of the ACM52 (2005), pp. 1–24. url:https://www.cs.jhu.edu/ ~baruch/teaching/600.427/Papers/oracle-STOC-try.pdf

2005
[28]

Compact routing schemes

Mikkel Thorup and Uri Zwick. “Compact routing schemes”. In: SPAA ’01. Crete Island, Greece: Association for Computing Machinery, 2001, pp. 1–10.isbn: 1581134096.doi:10 . 1145 / 378580 . 378581.url:https : //doi.org/10.1145/378580.378581

work page doi:10.1145/378580.378581 2001
[29]

Spanners and emulators with sublinear distance errors

Mikkel Thorup and Uri Zwick. “Spanners and emulators with sublinear distance errors”. In:Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm. SODA ’06. Miami, Florida: Society for Industrial and Applied Mathematics, 2006, pp. 802–809.isbn: 0898716055

2006
[30]

Greedy Completion for Weighted (α, β)-Spanners

Elad Tzalik. “Greedy Completion for Weighted (α, β)-Spanners”. In:arXivabs/2603.17047 (2026). eprint: 2603.17047(cs.DS).url:https://arxiv.org/abs/2603.17047

work page arXiv 2026
[31]

Additive spanners in nearly quadratic time

David P. Woodruff. “Additive spanners in nearly quadratic time”. In:Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming. ICALP’10. Bordeaux, France: Springer- Verlag, 2010, pp. 463–474.isbn: 3642141641

2010
[32]

Lower Bounds for Additive Spanners, Emulators, and More

David P. Woodruff. “Lower Bounds for Additive Spanners, Emulators, and More”. In:2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). 2006, pp. 389–398.doi:10.1109/FOCS.2006.45. A Runtime Efficient Construction In this section, we present Algorithm 4, which is a runtime efficient algorithm that essentially constructs the same 2· k...

work page doi:10.1109/focs.2006.45 2006
[33]

We assume without loss of generality thatp 1(w)∈ball(x, S 1, S2)

Case (c1):p 1(x)∈ball(w, S 1, S2) orp 1(w)∈ball(x, S 1, S2). We assume without loss of generality thatp 1(w)∈ball(x, S 1, S2). By Claim A.4 it follows that d[p1(w), x] =δ G(p1(w), x). The rest follows as inCase (c 1)from Lemma 6.5
[34]

Letibe the minimal such index

Case (c2):p 1(x)/∈ball(w, S 1, S2),p 1(w)/∈ball(x, S 1, S2) and there exists an 2≤i≤k−4 such thatp i(x)∈ball(p 1(w), Si , Si+2) orp i(w)∈ball(p 1(x), Si , Si+2). Letibe the minimal such index. By Claim A.5 it follows thatd[p i(x), p1(w)] =δ G(pi(x), p1(w)). The rest follows as inCase (c 2)from Lemma 6.5
[35]

In this case we introduce a slight modification to our case analysis

Case (c3):p 1(x)/∈ball(w, S 1, S2),p 1(w)/∈ball(x, S 1, S2) and for any 2≤i≤k−4 it holds thatp i(x)/∈ball(p1(w), Si , Si+2) andp i(w)/∈ball(p 1(x), Si , Si+2). In this case we introduce a slight modification to our case analysis. By Claim A.6 eitheru v⊆E k−1, in which case eitherd[p k−2(x), p1(w)] =δ G(pk−2(x), p1(w)) and we continue as inCase (c 3)from L...

[1] [1]

The 4/3 Additive Spanner Exponent Is Tight

Amir Abboud and Greg Bodwin. “The 4/3 Additive Spanner Exponent Is Tight”. In:J. ACM64.4 (Sept. 2017). issn: 0004-5411.doi:10.1145/3088511.url:https://doi.org/10.1145/3088511

work page doi:10.1145/3088511.url:https://doi.org/10.1145/3088511 2017

[2] [2]

A Hierarchy of Lower Bounds for Sublinear Additive Spanners

Amir Abboud, Greg Bodwin, and Seth Pettie. “A Hierarchy of Lower Bounds for Sublinear Additive Spanners”. In:SIAM Journal on Computing47.6 (2018), pp. 2203–2236.doi:10 . 1137 / 16M1105815. eprint:https : //doi.org/10.1137/16M1105815.url:https://doi.org/10.1137/16M1105815

work page doi:10.1137/16m1105815.url:https://doi.org/10.1137/16m1105815 2018

[3] [3]

On Additive Spanners in Weighted Graphs with Local Error

Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen Kobourov, and Richard Spence. “On Additive Spanners in Weighted Graphs with Local Error”. In:Graph-Theoretic Concepts in Computer Science. Ed. by Lukasz Kowalik, Micha l Pilipczuk, and Pawe l Rza˙ zewski. Cham: Springer International Publishing, 2021, pp. 361–373. isbn: 978-3-030-86838-3

2021

[4] [4]

Weighted Additive Spanners

Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen Kobourov, and Richard Spence. “Weighted Additive Spanners”. In:arXiv(2021). arXiv:2002.07152 [cs.DM].url:https://arxiv.org/abs/2002.07152

work page arXiv 2021

[5] [5]

Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)

Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. “Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)”. In:SIAM Journal on Computing28.4 (1999), pp. 1167–1181. doi:10.1137/S0097539796303421

work page doi:10.1137/s0097539796303421 1999

[6] [6]

Fast Construction of 4-Additive Spanners

Bandar Al-Dhalaan. “Fast Construction of 4-Additive Spanners”. In:arXivabs/2106.07152 (2021). arXiv: 2106.07152.url:https://arxiv.org/abs/2106.07152

work page arXiv 2021

[7] [7]

On sparse spanners of weighted graphs

Ingo Althofer, Gautam Das, David Dobkin, Deborah Joseph, and Jose Soares. “On sparse spanners of weighted graphs”. In:Discrete Comput. Geom.9.1 (Dec. 1993), pp. 81–100.issn: 0179-5376

1993

[8] [8]

Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs

Surender Baswana and Telikepalli Kavitha. “Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs”. In:SIAM Journal on Computing39.7 (2010), pp. 2865–2896.doi:10.1137/080737174. url:https://doi.org/10.1137/080737174

work page doi:10.1137/080737174 2010

[9] [9]

Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths

Surender Baswana and Telikepalli Kavitha. “Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths”. In:2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). Oct. 2006, pp. 591–602.doi:10.1109/FOCS.2006.29

work page doi:10.1109/focs.2006.29 2006

[10] [10]

Additive spanners and (α,β)- spanners

Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. “Additive spanners and (α,β)- spanners”. In:ACM Trans. Algorithms7.1 (Dec. 2010).issn: 1549-6325.doi:10.1145/1868237.1868242.url: https://doi.org/10.1145/1868237.1868242

work page doi:10.1145/1868237.1868242.url: 2010

[11] [11]

A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs

Surender Baswana and Sandeep Sen. “A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs”. In:Random Structures & Algorithms30.4 (2007), pp. 532–563.doi:https : //doi.org/10.1002/rsa.20130. eprint:https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20130. url:https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20130

work page doi:10.1002/rsa.20130 2007

[12] [12]

New (α, β) Spanners and Hopsets

Uri Ben-Levy and Merav Parter. “New (α, β) Spanners and Hopsets”. In:Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1695–1714.doi:10 . 1137 / 1 . 9781611975994 . 104.url: https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.104

work page doi:10.1137/1.9781611975994.104 2020

[13] [13]

New Additive Spanners

Shiri Chechik. “New Additive Spanners”. In:Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 498–512.doi:10.1137/1.9781611973105.36.url:https://epubs.siam. org/doi/abs/10.1137/1.9781611973105.36. 41

work page doi:10.1137/1.9781611973105.36.url:https://epubs.siam 2013

[14] [14]

All-Pairs Small-Stretch Paths

Edith Cohen and Uri Zwick. “All-Pairs Small-Stretch Paths”. In:Journal of Algorithms38.2 (1997), pp. 335– 353.issn: 0196-6774.doi:http://doi.org/10.1006/jagm.2000.1117.url:http://dl.acm.org/doi/pdf/10. 5555/314161.314190

work page doi:10.1006/jagm.2000.1117.url:http://dl.acm.org/doi/pdf/10 1997

[15] [15]

All-Pairs Almost Shortest Paths

Dorit Dor, Shay Halperin, and Uri Zwick. “All-Pairs Almost Shortest Paths”. In:SIAM Journal on Com- puting29.5 (2000), pp. 1740–1759.doi:10 . 1137 / S0097539797327908.url:https : / / doi . org / 10 . 1137 / S0097539797327908

2000

[16] [16]

Fast 2-Approximate All-Pairs Shortest Paths

Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams, and Tijn De Vos. “Fast 2-Approximate All-Pairs Shortest Paths”. In:arXiv(2023).doi:10.1137/1.9781611977912.169. arXiv:2307.09258 [cs.DS].url:https://arxiv.org/abs/2307.09258

work page doi:10.1137/1.9781611977912.169 2023

[17] [17]

Almost Shortest Paths with Near-Additive Error in Weighted Graphs

Michael Elkin, Yuval Gitlitz, and Ofer Neiman. “Almost Shortest Paths with Near-Additive Error in Weighted Graphs”. In:18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Ed. by Artur Czumaj and Qin Xin. Vol. 227. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur I...

work page doi:10.4230/lipics.swat.2022 2022

[18] [18]

Improved Weighted Additive Spanners

Michael Elkin, Yuval Gitlitz, and Ofer Neiman. “Improved Weighted Additive Spanners”. In:35th International Symposium on Distributed Computing (DISC 2021). Vol. 209. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2021, 21:1–21:15.isbn: 978-3-95977-210-5.doi:10 . 4230 / LIP...

work page doi:10.4230/lipics.disc.2021.21 2021

[19] [19]

(1 +ε·β)-spanner constructions for general graphs

Michael Elkin and David Peleg. “(1 +ε·β)-spanner constructions for general graphs”. In:Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. STOC ’01. Hersonissos, Greece: Association for Computing Machinery, 2001, pp. 173–182.isbn: 1581133499.doi:10.1145/380752.380797.url:https: //doi.org/10.1145/380752.380797

work page doi:10.1145/380752.380797.url:https: 2001

[20] [20]

Extremal problems in graph theory

Paul Erd˝ os. “Extremal problems in graph theory”. In:Proceedings of the Symposium on Theory of Graphs and Its Applications. Smolenice, Czechoslovakia, 1963, pp. 29–36

1963

[21] [21]

Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts

Shang-En Huang and Seth Pettie. “Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts”. In:SIAM Journal on Discrete Mathematics35.3 (2021), pp. 2129–2144.doi:10.1137/19M1306154. eprint:https://doi.org/10.1137/19M1306154.url:https://doi.org/10.1137/19M1306154

work page doi:10.1137/19m1306154 2021

[22] [22]

Thorup–Zwick emulators are universally optimal hopsets

Shang-En Huang and Seth Pettie. “Thorup–Zwick emulators are universally optimal hopsets”. In:Information Processing Letters142 (2019), pp. 9–13.issn: 0020-0190.doi:https://doi.org/10.1016/j.ipl.2018.10.001. url:https://www.sciencedirect.com/science/article/pii/S0020019018301868

work page doi:10.1016/j.ipl.2018.10.001 2019

[23] [23]

New Additive Emulators

Shimon Kogan and Merav Parter. “New Additive Emulators”. In:50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Ed. by Kousha Etessami, Uriel Feige, and Gabriele Puppis. Vol. 261. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2023, 85:1–85:...

work page doi:10.4230/lipics.icalp.2023 2023

[24] [24]

New weighted additive spanners

An La and Hung Le. “New weighted additive spanners”. In:arXiv(2024). arXiv:2408.14638 [cs.DS].url: https://arxiv.org/abs/2408.14638. 42

work page arXiv 2024

[25] [25]

In: Raman, V., Suresh, S.P

Liam Roditty and Ariel Sapir. “Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-Offs and Algorithms”. In:45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Ed. by C. Aiswarya, Ruta Mehta, and Subhajit Roy. Vol. 360. Leibniz International...

work page doi:10.4230/lipics.fsttcs 2025

[26] [26]

Faster Approximate All Pairs Shortest Paths

Barna Saha and Christopher Ye. “Faster Approximate All Pairs Shortest Paths”. In:Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). siam, 2023, pp. 4758–4827.doi:10.1137/ 1.9781611977912.170. eprint:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977912.170.url: https://epubs.siam.org/doi/abs/10.1137/1.9781611977912.170

work page doi:10.1137/1.9781611977912.170.url: 2024

[27] [27]

Approximate distance oracles

Mikkel Thorup and Uri Zwick. “Approximate distance oracles”. In:Journal of the ACM52 (2005), pp. 1–24. url:https://www.cs.jhu.edu/ ~baruch/teaching/600.427/Papers/oracle-STOC-try.pdf

2005

[28] [28]

Compact routing schemes

Mikkel Thorup and Uri Zwick. “Compact routing schemes”. In: SPAA ’01. Crete Island, Greece: Association for Computing Machinery, 2001, pp. 1–10.isbn: 1581134096.doi:10 . 1145 / 378580 . 378581.url:https : //doi.org/10.1145/378580.378581

work page doi:10.1145/378580.378581 2001

[29] [29]

Spanners and emulators with sublinear distance errors

Mikkel Thorup and Uri Zwick. “Spanners and emulators with sublinear distance errors”. In:Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm. SODA ’06. Miami, Florida: Society for Industrial and Applied Mathematics, 2006, pp. 802–809.isbn: 0898716055

2006

[30] [30]

Greedy Completion for Weighted (α, β)-Spanners

Elad Tzalik. “Greedy Completion for Weighted (α, β)-Spanners”. In:arXivabs/2603.17047 (2026). eprint: 2603.17047(cs.DS).url:https://arxiv.org/abs/2603.17047

work page arXiv 2026

[31] [31]

Additive spanners in nearly quadratic time

David P. Woodruff. “Additive spanners in nearly quadratic time”. In:Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming. ICALP’10. Bordeaux, France: Springer- Verlag, 2010, pp. 463–474.isbn: 3642141641

2010

[32] [32]

Lower Bounds for Additive Spanners, Emulators, and More

David P. Woodruff. “Lower Bounds for Additive Spanners, Emulators, and More”. In:2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). 2006, pp. 389–398.doi:10.1109/FOCS.2006.45. A Runtime Efficient Construction In this section, we present Algorithm 4, which is a runtime efficient algorithm that essentially constructs the same 2· k...

work page doi:10.1109/focs.2006.45 2006

[33] [33]

We assume without loss of generality thatp 1(w)∈ball(x, S 1, S2)

Case (c1):p 1(x)∈ball(w, S 1, S2) orp 1(w)∈ball(x, S 1, S2). We assume without loss of generality thatp 1(w)∈ball(x, S 1, S2). By Claim A.4 it follows that d[p1(w), x] =δ G(p1(w), x). The rest follows as inCase (c 1)from Lemma 6.5

[34] [34]

Letibe the minimal such index

Case (c2):p 1(x)/∈ball(w, S 1, S2),p 1(w)/∈ball(x, S 1, S2) and there exists an 2≤i≤k−4 such thatp i(x)∈ball(p 1(w), Si , Si+2) orp i(w)∈ball(p 1(x), Si , Si+2). Letibe the minimal such index. By Claim A.5 it follows thatd[p i(x), p1(w)] =δ G(pi(x), p1(w)). The rest follows as inCase (c 2)from Lemma 6.5

[35] [35]

In this case we introduce a slight modification to our case analysis

Case (c3):p 1(x)/∈ball(w, S 1, S2),p 1(w)/∈ball(x, S 1, S2) and for any 2≤i≤k−4 it holds thatp i(x)/∈ball(p1(w), Si , Si+2) andp i(w)/∈ball(p 1(x), Si , Si+2). In this case we introduce a slight modification to our case analysis. By Claim A.6 eitheru v⊆E k−1, in which case eitherd[p k−2(x), p1(w)] =δ G(pk−2(x), p1(w)) and we continue as inCase (c 3)from L...