Weighted Sparse and Lightweight Spanners with Local Additive Error
An additive +b spanner of a graph G is a subgraph which preserves shortest paths up to an additive +b 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 b cW whereW 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+e)W and (6+e)W spanners over vertex pairs P V x V on Oe(n|P| and Oe(n|P| edges for all e 0, which extend previously known unweighted results up to e dependence, as well as an all pairs +4W spanner on O(n) 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 +eW spanner with Oe(n) lightness, and a (4 e)W spanner with Oe(n lightness. These are the first known additive spanners with nontrivial lightness guarantees. All of the above spanners can be constructed in polynomial time.
ArXiv