Distributed Distance Approximation

Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard, Yuval Efron, Virginia Vassilevska Williams

TL;DR

This paper delivers a near-complete characterization of the trade-offs between approximation ratios and round complexity for fundamental distance parameters—diameter, radius, and eccentricities—in the CONGEST model of distributed computing. By introducing the algorithmic concept of an approximate pseudo-center and novel two-party communication complexity reductions, the authors resolve key complexity gaps for weighted, directed, and bi-chromatic graph settings.

What Problem Does This Paper Address?

In the classic CONGEST model, $n$ nodes communicate in synchronous rounds over a network by sending short $O(\log n)$-bit messages along graph edges. Fundamental global graph properties like the diameter (maximum shortest-path distance), radius (minimum eccentricity), and vertex eccentricities govern how fast information can propagate across the network.

Computing these parameters exactly requires $\tilde{\Omega}(n)$ rounds even on unweighted, undirected graphs—making exact global distance computation prohibitively slow for large networks. While approximation algorithms can run in sublinear time (e.g., $O(\sqrt{n} + D)$ rounds, where $D$ is the hop-diameter), the exact boundaries where problems transition from "fast" (sublinear round complexity) to "hard" ($\tilde{\Omega}(n)$ round complexity) remained poorly understood, particularly for weighted, directed, and bi-chromatic graphs (where distances are only evaluated between pairs of vertices having different colors, such as red and blue).

Methods

The paper develops both new algorithmic tools and lower-bound techniques:

  • Approximate Pseudo-Centers (Upper Bounds): Finding the exact graph center (the node minimizing eccentricity) requires $\tilde{\Omega}(n)$ rounds. Sequentially, Choudhary and Gold introduced pseudo-centers—small representative sets of vertices that approximate center-like properties. However, their construction relied on exact Single Source Shortest Path (SSSP) computations, which are expensive in CONGEST. The authors introduce the $\alpha$-approximate pseudo-center, showing that:
  • A small approximate pseudo-center (size $O(\log^2 n)$) can be constructed efficiently in CONGEST using approximate SSSP via randomized sampling.
  • Running approximate SSSP from this small set suffices to compute a $(2 + \varepsilon)$-approximation for diameter, radius, and all eccentricities.
  • Novel Communication Complexity Reductions (Lower Bounds): To prove matching lower bounds, the authors map hard two-party communication complexity problems to distributed graph constructions across a communication cut. Instead of relying solely on standard Set Disjointness or Equality, they introduce reductions using the Tribes (ListDISJ) function and the Hitting Set Existence (HSE) problem to CONGEST lower bounds.

Datasets

Not discussed in the paper. (The work is purely theoretical and does not evaluate on empirical datasets.)

Key Insights and Ideas

  • Bridging SSSP to Extremal Distance Approximations: Any $(1+\varepsilon)$-approximate directed weighted SSSP algorithm running in $T(n, \varepsilon, D)$ rounds can be directly translated into a $(2 + O(\varepsilon))$-approximation for diameter, radius, and all eccentricities in $\tilde{O}(T(n, \varepsilon, D) + D)$ rounds.
  • Sharp Phase Transitions in Approximation Ratios:
  • For weighted or directed radius, achieving an approximation ratio of $(2 - \varepsilon)$ is fundamentally hard, requiring $\tilde{\Omega}(n)$ rounds. Once an algorithm is allowed a factor of $(2 + \varepsilon)$, the complexity drops dramatically to sublinear time ($\tilde{O}(\sqrt{n} + D)$ for undirected and $\tilde{O}(\sqrt{n}D^{1/4} + D)$ for directed graphs).
  • Any finite multiplicative approximation $\alpha(n)$ to weighted or directed radius/diameter still requires $\tilde{\Omega}(\sqrt{n} + D)$ rounds.
  • Bi-Chromatic Distance Boundaries: In bi-chromatic graphs (where distances are measured only between sets $S$ and $V \setminus S$), the transition point changes: computing a $(5/3 - \varepsilon)$-approximation to bi-chromatic diameter requires $\tilde{\Omega}(n)$ rounds, while a $5/3$-approximation can be achieved in $\tilde{O}(\sqrt{n} + D)$ rounds on unweighted graphs.

Key Results

  • Directed & Weighted Approximations:
  • $(2 + \varepsilon)$-approximation for radius, diameter, and eccentricities in $\tilde{O}(\sqrt{n} + D)$ rounds for non-negative weighted undirected graphs, and $\tilde{O}(\sqrt{n}D^{1/4} + D)$ rounds for directed graphs.
  • An exact SSSP subroutine yields a 2-approximation in $\tilde{O}(\sqrt{n}D^{1/4} + D)$ rounds on directed weighted graphs.
  • Lower Bounds:
  • Proved that any randomized algorithm achieving a $(2 - \varepsilon)$-approximation of the weighted or directed radius requires $\tilde{\Omega}(n)$ rounds.
  • Proved that any $\alpha(n)$-approximation of weighted/directed radius or diameter requires $\tilde{\Omega}(\sqrt{n} + D)$ rounds.
  • Bi-Chromatic Distances:
  • Presented a $5/3$-approximation algorithm for bi-chromatic diameter running in $\tilde{O}(\sqrt{n} + D)$ rounds (unweighted, undirected).
  • Proved that achieving $(5/3 - \varepsilon)$-approximation for bi-chromatic diameter requires $\tilde{\Omega}(n / \log^3 n)$ rounds, making the $5/3$ bound tight.
  • Proved that achieving $(2 - \varepsilon)$-approximation for directed bi-chromatic diameter requires $\tilde{\Omega}(n / \log^2 n)$ rounds.

Limitations and Future Work

  • The $[3/2, 2]$ Gap for Directed Diameter: While upper bounds achieve $2$ (or $2+\varepsilon$) and lower bounds rule out $<3/2$ in sublinear rounds, pinning down the exact optimal approximation ratio in the range $[3/2, 2]$ for directed diameter remains open.
  • Unweighted, Undirected Radius: Characterizing the tight complexity trade-off in the approximation range $[3/2, 2)$ for unweighted, undirected radius remains unresolved.
  • Deterministic Bounds: Several upper bounds rely on randomized Las Vegas or high-probability routines; closing the performance gap between randomized and deterministic distributed APSP/SSSP algorithms remains an ongoing challenge in the CONGEST model.

Summary updated

Abstract

Diameter, radius and eccentricities are fundamental graph parameters, which are extensively studied in various computational settings. Typically, computing approximate answers can be much more efficient compared with computing exact solutions. In this paper, we give a near complete characterization of the trade-offs between approximation ratios and round complexity of distributed algorithms for approximating these parameters, with a focus on the weighted and directed variants. Furthermore, we study bi-chromatic variants of these parameters defined on a graph whose vertices are colored either red or blue, and one focuses only on distances for pairs of vertices that are colored differently. Motivated by applications in computational geometry, bi-chromatic diameter, radius and eccentricities have been recently studied in the sequential setting [Backurs et al. STOC'18, Dalirrooyfard et al. ICALP'19]. We provide the first distributed upper and lower bounds for such problems. Our technical contributions include introducing the notion of approximate pseudo-center, which extends the pseudo-centers of [Choudhary and Gold SODA'20], and presenting an efficient distributed algorithm for computing approximate pseudo-centers. On the lower bound side, our constructions introduce the usage of new functions into the framework of reductions from 2-party communication complexity to distributed algorithms.
BibTeX
@inproceedings{ancona2020distributed,
  author = {Bertie Ancona and Keren Censor-Hillel and Mina Dalirrooyfard and Yuval Efron and Virginia Vassilevska Williams},
  title = {{Distributed Distance Approximation}},
  booktitle = {OPODIS},
  year = {2020},
  url = {https://openreview.net/forum?id=chm0q7Xcfi},
}

Loading related content...

Figure