Having Hope in Missing Spanners: New Distance Preservers and Light Hopsets
Shimon Kogan, Merav Parter · Society for Industrial and Applied Mathematics eBooks · 2025
An r-missing spanner for a graph G is a sparse subgraph H ⊆ G satisfying that for any u, v pair there is a (possibly approximate) u-v shortest path P in G such that |P \ H| ≤ r. That is, H misses at most r edges from every u-v (approximate) shortest path. [Kogan and Parter, FOCS ’22] introduced the notion of missing spanners as an intermediate step for translating hopset constructions into spanners and distance preservers.