Abstract:
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, Chekuri and Motwani, we describe an \tilde{O}(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 \tilde{O}(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 \tilde{O}(n^2) time algorithm \APASP_\infty for producing stretch 3 estimated distances in an unweighted and undirected graph on n vertices. No constant stretch factor was previously achieved in \tilde{O}(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 in V we have \delta_G(u,v) <= \delta_F(u,v) <= \delta_G(u,v)+k. We show that every unweighted graph on n vertices has a 2-emulator with \tilde{O}(n^{3/2}) edges and a 4-emulator with \tilde{O}(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 \tilde{O}(n^{3/2}) edges and that such a 3-spanner can be built in \tilde{O}(mn^{1/2}) time. We also describe an \tilde{O}(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. A preliminary version of this paper appeared at FOCS'96.