All-pairs almost shortest paths

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 Aingworth et al. [SIAM J. Comput., 28 (1999), pp. 1167 1181], we describe an (O) over tilde(min{n(3/2)m(1/2),n(7/3)})-time algorithm APASP(2) for computing all distances in G with an additive one-sided error of at most 2. Algorithm APASP(2) is simple, easy to implement, and faster than the fastest known matrix-multiplication algorithm. Furthermore, for every even k > 2, we describe an (O) over tilde(min{n(2-2/(k+2))m(2/(k+2)),n(2+2/(3k-2))})-time algorithm APASP(k) for computing all distances in G with an additive one-sided error of at most k. We also give an (O) over tilde(n(2))-time algorithm APASP(infinity) for producing stretch 3 estimated distances in an unweighted and undirected graph on n vertices. No constant stretch factor was previously achieved in (O) over tilde(n(2)) time. We say that a weighted graph F = (V, E') k-emulates an unweighted graph G = (V, E) if for every u, v is an element of V we have delta(G)(u, v) less than or equal to delta(F)(u, v) less than or equal to delta(G)(u, v) + k. We show that every unweighted graph on n vertices has a 2-emulator with (O) over tilde(n(3/2)) edges and a 4-emulator with (O) over tilde(n(4/3)) edges. These results are asymptotically tight. Finally, we show that any weighted undirected graph on n vertices has a 3-spanner with (O) over tilde(n(3/2)) edges and that such a 3-spanner can be built in (O) over tilde(mn(1/2)) time. We also describe an (O) over tilde(n(m(2/3)+n))-time algorithm for estimating all distances in a weighted undirected graph on n vertices with a stretch factor of at most 3.