Sparse distance preservers and additive spanners

Abstract

For an unweighted graph G = (V,E), G′ = (V,E′) is a subgraph if E′ ⊆ E, and G″ = (V″, E′, ω) is a Steiner graph if V ⊆ V″, and for any pair of vertices u, w ∈ V, the distance between them in G″ (denoted d G″(u,w)) is at least the distance between them in G (denoted d G(u,w)). In this paper we introduce the notion of distance preserver. A subgraph (resp., Steiner graph) G′ of a graph G is a subgraph (resp., Steiner) D-preserver of G if for every pair of vertices u, w ∈ V with d G(u,w) ≥ D, d G′(u, w) = d G(u, w). We show that any graph (resp., digraph) has a subgraph D-preserver with at most O(n 2/D) edges (resp., arcs), and there are graphs and digraphs for which any undirected Steiner D-preserver contains Ω(n 2/D) edges. However, we show that if one allows a directed Steiner (diSteiner) D-preserver, then these bounds can be improved. Specifically, we show that for any graph or digraph there exists a diSteiner D-preserver with O(n 2·log D/D·log n) arcs, and that this result is tight up to a constant factor. We also study D-preserving distance labeling schemes, that are labeling schemes that guarantee precise calculation of distances between pairs of vertices that are at a distance of at least D one from another. We show that there exists a D-preserving labeling scheme with labels of size O(n/D log 2 n), and that labels of size Ω(n/D log D) are required for any D-preserving labeling scheme. © 2006 Society for Industrial and Applied Mathematics.