We introduce the following notion of compressing an undirected graph G with edge-lengths and terminal vertices @math . A distance-preserving minor is a minor G' (of G) with possibly different edge-lengths, such that @math and the shortest-path distance between every pair of terminals is exactly the same in G and in G'. What is the smallest f*(k) such that every graph G with k=|R| terminals admits a distance-preserving minor G' with at most f*(k) vertices? Simple analysis shows that @math . Our main result proves that @math , significantly improving over the trivial @math . Our lower bound holds even for planar graphs G, in contrast to graphs G of constant treewidth, for which we prove that O(k) vertices suffice.
Coppersmith and Elkin @cite_11 studied a problem similar to ours, except that they seek subgraphs with few edges (rather than minors). Among other things, they prove that for every weighted graph @math and every set of @math terminals (sources), there exists a weighted subgraph @math , called , that preserves terminal distances exactly and has @math edges. They also show a nearly-matching lower bound on @math . Dor, Halperin and Zwick @cite_9 similarly asked for a graph with few edges, though not necessarily a subgraph or a minor, that preserves all distances. Woodruff @cite_5 combined their notion of with Coppersmith and Elkin's , and studied the size of arbitrary graphs preserving only distances between given sets of terminals (sources) in the given graph @math .
@cite_5 @cite_9 @cite_11
1972920042 2156047991 2031536548
An additive spanner of an unweighted undirected graph G with distortion d is a subgraph H such that for any two vertices u, v G, we have _H ( u,v ) = _G ( u,v ) + d. For every k = O ( n n ), we construct a graph G on n vertices for which any additive spanner of G with distortion 2k - 1 has ( 1 k n^ 1 + 1 k ) edges. This matches the lower bound previously known only to hold under a 1963 conjecture of Erdos. We generalize our lower bound in a number of ways. First, we consider graph emulators introduced by Dor, Halperin, and Zwick (FOCS, 1996), where an emulator of an unweighted undirected graph G with distortion d is like an additive spanner except H may be an arbitrary weighted graph such that _G ( u,v ) _H ( u,v ) _G ( u,v ) + d. We show a lower bound of ( 1 k^2 n^ 1 + 1 k ) edges for distortion-(2k - 1) emulators. These are the first non-trivial bounds for k 3. Second, we parameterize our bounds in terms of the minimum degree of the graph. Namely, for minimum degree n^ 1 k+c for any c 0, we prove a bound of ( 1 k n^ 1 + 1 k - c(1 + 2 (k - 1)) ) for additive spanners and ( 1 k^2 n^ 1 + 1 k - c(1 + 2 (k - 1)) ) for emulators. For k = 2 these can be improved to ( n^ 3 2 - c ). This partially answers a question of (SODA, 2005) for additive spanners. Finally, we continue the study of pair-wise and source-wise distance preservers defined by Coppersmith and Elkin (SODA, 2005) by considering their approximate variants and their relaxation to emulators. We prove the first lower bounds for such graphs. Let G=(V,E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most 1 is as hard as Boolean matrix multiplication. Building on recent work of [SIAM J. Comput., 28 (1999), pp. 1167--1181], we describe an @math -time algorithm APASP2 for computing all distances in G with an additive one-sided error of at most 2. Algorithm APASP2 is simple, easy to implement, and faster than the fastest known matrix-multiplication algorithm. Furthermore, for every even k>2, we describe an @math -time algorithm APASPk for computing all distances in G with an additive one-sided error of at most k. We also give an @math -time algorithm @math for producing stretch 3 estimated distances in an unweighted and undirected graph on n vertices. No constant stretch factor was previously achieved in @math time. We say that a weighted graph F=(V,E') k-emulates an unweighted graph G=(V,E) if for every @math we have @math . We show that every unweighted graph on n vertices has a 2-emulator with @math edges and a 4-emulator with @math edges. These results are asymptotically tight. Finally, we show that any weighted undirected graph on n vertices has a 3-spanner with @math edges and that such a 3-spanner can be built in @math time. We also describe an @math -time algorithm for estimating all distances in a weighted undirected graph on n vertices with a stretch factor of at most 3. 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.