An additive \(+\beta\) spanner of a graph \(G\) is a subgraph which preserves distances up to an additive \(+\beta\) error. Additive spanners are well-studied in unweighted graphs but have only recently received attention in weighted graphs [Elkin et al. 2019 and 2020, Ahmed et al. 2020]. This paper makes two new contributions to the theory of weighted additive spanners. For weighted graphs, [Ahmed et al. 2020] provided constructions of sparse spanners with global error \(\beta=cW\), where \(W\) is the maximum edge weight in \(G\) and \(c\) is constant. We improve these to local error by giving spanners with additive error \(+cW(s,t)\) for each vertex pair \((s,t)\), where \(W(s,t)\) is the maximum edge weight along the shortest \(s\)–\(t\) path in \(G\). These include pairwise \(+(2+\varepsilon)W(\cdot,\cdot)\) and \(+(6+\varepsilon) W(\cdot, \cdot)\) spanners over vertex pairs \(\mathcal{P} \subseteq V \times V\) on \(O_{\varepsilon}(n|\mathcal{P}|^{1/3})\) and \(O_{\varepsilon}(n|\mathcal{P}|^{1/4})\) edges for all \(\varepsilon>0\), which extend previously known unweighted results up to \(\varepsilon\) dependence, as well as an all-pairs \(+4W(\cdot,\cdot)\) spanner on \(\tilde{O}(n^{7/5})\) edges. Besides sparsity, another natural way to measure the quality of a spanner in weighted graphs is by its lightness, defined as the total edge weight of the spanner divided by the weight of a minimum spanning tree of \(G\). We provide a \(+\varepsilon W(\cdot,\cdot)\) spanner with \(O_{\varepsilon}(n)\) lightness, and a \(+(4+\varepsilon) W(\cdot,\cdot)\) spanner with \(O_{\varepsilon}(n^{2/3})\) lightness. These are the first known additive spanners with nontrivial lightness guarantees. All of the above spanners can be constructed in polynomial time.
Based on a paper by Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen Kobourov, and Richard Spence, arXiv:2103.09731.