2021/03/17 by Ahmed, Reyan, Bodwin, Greg, Hamm, Keaton +2 · 1 citation
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2103.09731
An additive +β spanner of a graph G is a subgraph which preserves distances up to an additive +β 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 β= 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+\eps)W(⋅,⋅) and +(6+\eps) W(⋅, ⋅) spanners over vertex pairs \Pc ⊆ V × V on O\eps(n|\Pc|1/3) and O\eps(n|\Pc|1/4) edges for all \eps > 0, which extend previously known unweighted results up to \eps dependence, as well as an all-pairs +4W(⋅,⋅) spanner on \widetildeO(n7/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 an MST of G. We provide a +\eps W(⋅,⋅) spanner with O\eps(n) lightness, and a +(4+\eps) W(⋅,⋅) spanner with O\eps(n2/3) lightness. These are the first known additive spanners with nontrivial lightness guarantees. All of the above spanners can be constructed in polynomial time.