Improved All-Pairs Approximate Shortest Paths in Congested Clique

In this paper, we present new algorithms for approximating All-Pairs Shortest Paths (APSP) in the Congested Clique model. We present randomized algorithms for weighted undirected graphs. Our first contribution is an O (1) -approximate APSP algorithm taking just O (n) rounds. Prior to our work, the fastest algorithms that give an O (1) -approximation for APSP take poly (n) rounds in weighted undirected graphs, and poly (n) rounds in unweighted undirected graphs. If we terminate the execution of the algorithm early, we obtain an O (t) -round algorithm that yields an O ( (n) ^1/2ᵗ) distance approximation for a parameter t. The trade-off between t and the approximation quality provides flexibility for different scenarios, allowing the algorithm to adapt to specific requirements. In particular, we can get an O ( (n) ^1/2ᵗ) -approximation for any constant t in O (1) -rounds. Such result was previously known only for the special case that t=0. A key ingredient in our algorithm is a lemma that allows to improve an O (a) -approximation for APSP to an O (a) -approximation for APSP in O (1) rounds. To prove the lemma, we develop several new tools, including O (1) -round algorithms for computing the k closest nodes, a certain type of hopset, and skeleton graphs.