This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases. Because of the need to simultaneously make decisions at far apart locations, the algorithms use additional mechanisms compared to their sequential counterparts. We complement our algorithms with a lower bound on the number of rounds required for computing pairwise spanners. The standard reductions from set-disjointness and equality seem unsuitable for this task because no specific edge needs to be removed from the graph. Instead, to obtain our lower bound, we define a new communication complexity problem that reduces to computing a sparse spanner, and prove a lower bound on its communication complexity using information theory. This technique significantly extends the current toolbox used for obtaining lower bounds for the CONGEST model, and we believe it may find additional applications.
We introduce and study the notions of pairwise and sourcewise preservers. Given an undirected N-vertex graph G = (V,E) and a set P of pairs of vertices, let G' = (V,H), H E, be called a pairwise preserver of G with respect to P if for every pair u,w P, distG'(u,w) = distG(u,w). For a set S V of sources, a pairwise preserver of G with respect to the set of all pairs P = (S 2) of sources is called a sourcewise preserver of G with respect to S. We prove that for every undirected possibly weighted N-vertex graph G and every set P of P = O(N1 2) pairs of vertices of G, there exists a linear-size pairwise preserver of G with respect to P. Consequently, for every subset S V of S = O(N1 4) sources, there exists a linear-size sourcewise preserver of G with respect to S. On the negative side we show that neither of the two exponents (1 2 and 1 4) can be improved even when the attention is restricted to unweighted graphs. Our lower bounds involve constructions of dense convexly independent sets of vectors with small Euclidean norms. We believe that the link between the areas of discrete geometry and spanners that we establish is of independent interest and might be useful in the study of other problems in the area of low-distortion embeddings. For an unweighted graph @math , @math is a subgraph if @math , and @math is a Steiner graph if @math , and for any pair of vertices @math , the distance between them in @math (denoted @math ) is at least the distance between them in @math (denoted @math ). In this paper we introduce the notion of distance preserver. A subgraph (resp., Steiner graph) @math of a graph @math is a subgraph (resp., Steiner) @math -preserver of @math if for every pair of vertices @math with @math , @math . We show that any graph (resp., digraph) has a subgraph @math -preserver with at most @math edges (resp., arcs), and there are graphs and digraphs for which any undirected Steiner @math -preserver contains @math edges. However, we show that if one allows a directed Steiner (diSteiner) @math -preserver, then these bounds can be improved. Specifically, we show that for any graph or digraph there exists a diSteiner @math -preserver with @math arcs, and that this result is tight up to a constant factor. We also study @math -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 @math one from another. We show that there exists a @math -preserving labeling scheme with labels of size @math , and that labels of size @math are required for any @math -preserving labeling scheme. 