Fast estimation of diameter and shortest paths (without matrix multiplication)

In the recent past, there has been considerable progress in devising algori thms for the all-pairs shortest paths (APSP) problem running in time signif icantly smaller than the obvious time bound of O(n(3)). Unfortunately, all the new algorithms are based on fast matrix multiplication algorithms that are notoriously impractical. Our work is motivated by the goal of devising purely combinatorial algorithms that match these improved running times. Ou r results come close to achieving this goal, in that we present algorithms with a small additive error in the length of the paths obtained. Our algori thms are easy to implement, have the desired property of being combinatoria l in nature, and the hidden constants in the running time bound are fairly small. Our main result is an algorithm which solves the APSP problem in unweighted , undirected graphs with an additive error of 2 in time O(n(2.5) root log n ). This algorithm returns actual paths and not just the distances. In addit ion, we give more efficient algorithms with running time O(n(1.5) root k lo g n + n(2) log(2) n) for the case where we are only required to determine s hortest paths between k specified pairs of vertices rather than all pairs o f vertices. The starting point for all our results is an O(m root n log n) algorithm for distinguishing between graphs of diameter 2 and 4, and this i s later extended to obtaining a ratio 2/3 approximation to the diameter in time O(m root n log n + n(2) log n). Unlike in the case of APSP, our result s for approximate diameter computation can be extended to the case of direc ted graphs with arbitrary positive real weights on the edges.