All-pairs nearly 2-approximate shortest paths in O(n²polylog n) time

Abstract

Let G=(V,E) be an unweighted undirected graph on |V|=n vertices and |E|=m edges. Let δ(u,v) denote the distance between vertices u,v∈V. An algorithm is said to compute all-pairs t-approximate shortest-paths/distances, for some t≥1, if for each pair of vertices u,v∈V, the path/distance reported by the algorithm is not longer/greater than t·δ(u,v). This paper presents two extremely simple randomized algorithms for computing all-pairs nearly 2-approximate distances. The first algorithm requires an expected O(m^2/3nlogn+n²) time, and for any u,v∈V reports a distance no greater than 2δ(u,v)+1. Our second algorithm requires an expected O(n²log^3/2) time, and for any u,v∈V reports a distance bounded by 2δ(u,v)+3. This paper also presents the first expected O(n²) time algorithm to compute all-pairs 3-approximate distances.