Computing Exact Distances in the Congested Clique

Abstract

This paper gives simple distributed algorithms for the fundamental problem of computing graph distances in the Congested Clique model. One of the main components of our algorithms is fast matrix multiplication, for which we show an \(O(n^{1/3})\)-round algorithm when the multiplication needs to be performed over a semi-ring, and an \(O(n^{0.157})\)-round algorithm when the computation can be performed over a field. We propose to denote by \(\kappa\) the exponent of matrix multiplication in this model, which gives \(\kappa < 0.157\). We show how to compute all-pairs-shortest-paths (APSP) in \(O(n^{1/3}\log{n})\) rounds in weighted graphs of \(n\) nodes, implying also the computation of the graph diameter \(D\). In unweighted graphs, APSP can be computed in \(O(\min\{n^{1/3}\log{D},n^{\kappa} D\})\) rounds, and the diameter can be computed in \(O(n^{\kappa}\log{D})\) rounds. Furthermore, we show how to compute the girth of a graph in \(O(n^{1/3})\) rounds, and provide triangle detection and 4-cycle detection algorithms that complete in \(O(n^{\kappa})\) rounds. All our algorithms are deterministic. Our triangle detection and 4-cycle detection algorithms improve upon the previously best known algorithms in this model, and refute a conjecture that \(\tilde \Omega (n^{1/3})\) rounds are required for detecting triangles by any deterministic oblivious algorithm. Our distance computation algorithms are exact, and improve upon the previously best known \(\tilde O(n^{1/2})\) algorithm of Nanongkai [STOC 2014] for computing a \((2+o(1))\)-approximation of APSP. Finally, we give lower bounds that match the above for natural families of algorithms. For the Congested Clique Broadcast model, we derive unconditioned lower bounds for matrix multiplication and APSP. The matrix multiplication algorithms and lower bounds are adapted from parallel computations, which is a connection of independent interest.