# Approximation of Distances and Shortest Paths in the Broadcast Congest Clique

Preprint · Stephan Holzer, Nathan Pinsker

- Archive id: arxiv:1412.3445
- Published: 2014-12-10
- arXiv: https://arxiv.org/abs/1412.3445
- Source URL: https://arxiv.org/abs/1412.3445
- PDF: https://arxiv.org/pdf/1412.3445
- Provenance: arxiv

## Abstract

We study the broadcast version of the CONGEST CLIQUE model of distributed computing. In this model, in each round, any node in a network of size $n$ can send the same message (i.e. broadcast a message) of limited size to every other node in the network. Nanongkai presented in \[STOC'14\] a randomized $(2+o(1))$-approximation algorithm to compute all pairs shortest paths (APSP) in time $\\tilde{O}(\\sqrt{n})$ on weighted graphs, where we use the convention that $\\tildeΩ(f(n))$ is essentially $Ω(f(n)/$polylog$f(n))$ and $\\tilde{O}(f(n))$ is essentially $O(f(n) $polylog$f(n))$. We complement this result by proving that any randomized $(2-o(1))$-approximation of APSP and $(2-o(1))$-approximation of the diameter of a graph takes $\\tildeΩ(n)$ time in the worst case. This demonstrates that getting a negligible improvement in the approximation factor requires significantly more time. Furthermore this bound implies that already computing a $(2-o(1))$-approximation of all pairs shortest paths is among the hardest graph-problems in the broadcast-version of the CONGEST CLIQUE model and contrasts a recent $(1+o(1))$-approximation for APSP that runs in time $O(n^{0.15715})$ in the unicast version of the CONGEST CLIQUE model. On the positive side we provide a deterministic version of Nanongkai's $(2+o(1))$-approximation algorithm for APSP. To do so we present a fast deterministic construction of small hitting sets. We also show how to replace another randomized part within Nanongkai's algorithm with a deterministic source-detection algorithm designed for the CONGEST model presented by Lenzen and Peleg at PODC'13.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.