Constant-Round Near-Optimal Spanners in Congested Clique
Shiri Chechik, Tianyi Zhang · 2022
Graph spanners have been extensively studied in the literature of graph algorithms. In an undirected weighted graph G = (V, E,ω) on n vertices, a t-spanner of G is a subgraph that preserves pairwise distances up to a multiplicative stretch factor of t . It is well-known that, for any integer k, a (2k - 1)-spanner with O(n1+1/k ) edges always exists, and the stretch-sparsity balance is tight under the girth conjecture by Erdos. In this paper, we are interested in efficient algorithms for spanners in the distributed setting. Specifically, we present constant-round congested clique algorithms for spanners with nearly optimal stretch-sparsity trade-offs: (2k-1)-spanners with O(n1+1/k ) edges in unweighted graphs (i.e. ω ≡ 1). (1 + ε) (2k - 1)-spanners with O(n1+1/k ) edges in weighted graphs. (2k-1)-spanners withO(kn1+1/k ) edges in weighted graphs.