In this work we present the first constant-round algorithms for computing spanners and approximate All-Pairs Shortest Paths (APSP) in the distributed Congested Clique model. Specifically, we show the following results for undirected n-node graphs.<UnorderedList Mark="Bullet"> <ItemContent> For every integer <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(k \ge 1\)</EquationSource> </InlineEquation>, O(1)-round algorithms for constructing O(k)-spanners with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(O(n^{1+1/k})\)</EquationSource> </InlineEquation> edges in unweighted graphs, and O(k)-spanners with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(O(n^{1+1/k} \log {n})\)</EquationSource> </InlineEquation> edges in weighted graphs. </ItemContent> <ItemContent> An O(1)-round algorithm for <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(O(\log {n})\)</EquationSource> </InlineEquation>-approximation for APSP in unweighted graphs. </ItemContent> <ItemContent> An O(1)-round algorithm for <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(O(\log ^2{n})\)</EquationSource> </InlineEquation>-approximation for APSP in weighted graphs. </ItemContent> </UnorderedList> All our algorithms are randomized and succeed with high probability. Prior to our work, the fastest algorithms for computing O(k)-spanners in this model require <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\({{\,\textrm{poly}\,}}(\log {k})\)</EquationSource> </InlineEquation> rounds [Parter, Yogev, DISC ’18] [Biswas, Dory, Ghaffari, Mitrovic, Nazari, SPAA ’21], and the fastest algorithms for approximate shortest paths require <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\({{\,\textrm{poly}\,}}(\log {\log {n}})\)</EquationSource> </InlineEquation> rounds [Dory, Parter, PODC ’20]. Our results extend to the closely related massively parallel computation (MPC) model with near-linear memory per machine, leading to the first O(1)-round algorithms for spanners and approximate shortest paths in this model as well.

Constant-round spanners and shortest paths in congested clique and MPC

期刊论文
出版模式：

开放获取
发表日期：

2026年3月18日

查看全文

Michal Dory,
Orr Fischer,
Seri Khoury,
Dean Leitersdorf

摘要

In this work we present the first constant-round algorithms for computing spanners and approximate All-Pairs Shortest Paths (APSP) in the distributed Congested Clique model. Specifically, we show the following results for undirected n-node graphs.

For every integer \(k \ge 1\) , O(1)-round algorithms for constructing O(k)-spanners with \(O(n^{1+1/k})\) edges in unweighted graphs, and O(k)-spanners with \(O(n^{1+1/k} \log {n})\) edges in weighted graphs.

An O(1)-round algorithm for \(O(\log {n})\) -approximation for APSP in unweighted graphs.

An O(1)-round algorithm for \(O(\log ^2{n})\) -approximation for APSP in weighted graphs.

All our algorithms are randomized and succeed with high probability. Prior to our work, the fastest algorithms for computing O(k)-spanners in this model require \({{\,\textrm{poly}\,}}(\log {k})\) rounds [Parter, Yogev, DISC ’18] [Biswas, Dory, Ghaffari, Mitrovic, Nazari, SPAA ’21], and the fastest algorithms for approximate shortest paths require \({{\,\textrm{poly}\,}}(\log {\log {n}})\) rounds [Dory, Parter, PODC ’20]. Our results extend to the closely related massively parallel computation (MPC) model with near-linear memory per machine, leading to the first O(1)-round algorithms for spanners and approximate shortest paths in this model as well.