New weighted additive spanners

Ahmed, Bodwin, Sahneh, Kobourov, and Spence (WG 2020) introduced additive spanners for weighted graphs and constructed (i) a +2Wₘₐₓ spanner with O(n3/2) edges and (ii) a +4Wₘₐₓ spanner with Õ(n7/5) edges, and (iii) a +8Wₘₐₓ spanner with O(n4/3) edges, for any weighted graph with n vertices. Here Wₘₐₓ = maxe∈ Ew(e) is the maximum edge weight in the graph. Their results for +2Wₘₐₓ, +4Wₘₐₓ, and +8Wₘₐₓ match the state-of-the-art bounds for the unweighted counterparts where Wₘₐₓ = 1. They left open the question of constructing a +6Wₘₐₓ spanner with O(n4/3) edges. Elkin, Gitlitz, and Neiman (DISC 2021) made significant progress on this problem by showing that there exists a +(6+ε)Wₘₐₓ spanner with O(n4/3/ε) edges for any fixed constant ε > 0. Indeed, their result is stronger as the additive stretch is local: the stretch for any pair $u,v$ is +(6+ε)Wᵤᵥ where Wᵤᵥ is the maximum weight edge on the shortest path from u to v. In this work, we resolve the problem posted by Ahmed et al. (WG 2020) up to a poly-logarithmic factor in the number of edges: We construct a +6Wₘₐₓ spanner with Õ(n4/3) edges. We extend the construction for $+6$-spanners of Woodruff (ICALP 2010), and our main contribution is an analysis tailoring to the weighted setting. The stretch of our spanner could also be made local, in the sense of Elkin, Gitlitz, and Neiman (DISC 2021). We also study the fast constructions of additive spanners with +6Wₘₐₓ and +4Wₘₐₓ stretches. We obtain, among other things, an algorithm for constructing a +(6+ε)Wₘₐₓ spanner of Õ(n4/3ε) edges in Õ(n²) time.