May 21, 2021, 1:00 – 1:50:
On Additive Spanners in Weighted Graphs with Local Error
Hadi Khodabandeh
An additive spanner of a graph 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 , where is the maximum edge
weight in and is constant. We improve these to local
error by giving spanners with additive error for each
vertex pair , where is the maximum edge weight along
the shortest – path in . These include pairwise
and spanners over vertex pairs
on and
edges for all
, which extend previously known unweighted results up
to dependence, as well as an all-pairs
spanner on 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 . We provide a spanner with
lightness, and a spanner with
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.