Sparse Distance Preservers and Additive Spanners

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 dG'(u,w)) is at least the distance between them in G (denoted dG(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 dG(u,w) ≥ D, dG'(u,w) = dG(u,w). We show that any graph (resp., digraph) has a subgraph D-preserver with at most O(n²/D) edges (resp., arcs), and there are graphs and digraphs for which any undirected Steiner D-preserver contains Ω(n²/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² · 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² n), and that labels of size Ω(n D log D) are required for any D-preserving labeling scheme.