Sparse Distance Preservers and Additive Spanners
Béla Bollobás, Don Coppersmith, Michael Elkin · SIAM Journal on Discrete Mathematics · 2005
For an unweighted graph $G = (V,E)$, $G' = (V,E')$ is a subgraph if $E' \subseteq E$, and $G' = (V',E',\omega)$ is a Steiner graph if $V \subseteq V'$, and for any pair of vertices $u,w \in 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 \in V$ with $d_G(u,w) \ge 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 $\Omega(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 \cdot \log D} \over {D \cdot \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} \over {D}} \log^2 n)$, and that labels of size $\Omega({{n} \over {D}} \log D)$ are required for any D-preserving labeling scheme.