Distributed Distance Approximation

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

Abstract: Diameter, radius, and eccentricities are fundamental graph parameters 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, focusing only on distances for pairs of vertices that are colored differently. 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 previous work, and presenting an efficient distributed algorithm for computing them. 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.

Introduction

In distributed computing, particularly within the CONGEST model, nodes in a network must collaborate to determine global properties like the diameter (the longest shortest path), the radius (the minimum distance from a central node to the farthest node), and eccentricities (the maximum distance from a specific node to any other). In this model, communication is restricted to $O(\log n)$ bits per edge per round.

Finding exact values for these parameters is notoriously slow, typically requiring $\tilde{\Omega}(n)$ rounds, where $n$ is the number of nodes. While approximations for simple undirected graphs have been well-documented, the landscape for weighted and directed graphs remained incomplete until now. This research fills those gaps and introduces the first distributed analysis of bi-chromatic distance parameters.

Upper Bounds and Algorithmic Landscape

The paper provides a comprehensive suite of new algorithms that push the boundaries of what is achievable in sublinear time. A central result is the development of a $(2+\epsilon)$-approximation algorithm for diameter, radius, and eccentricities. In undirected weighted graphs, this algorithm runs in $\tilde{O}(\sqrt{n} + D)$ rounds, where $D$ is the hop-diameter. For directed graphs, the complexity is $\tilde{O}(\sqrt{n}D^{1/4} + D)$.

Summary of distributed upper bounds for distance parameters.

These algorithms leverage a new technique called approximate pseudo-centers. Instead of attempting to locate the single optimal "center" node—a task that is computationally expensive in a distributed setting—the authors identify a small "committee" or set of nodes $C$. This set is constructed such that every node's eccentricity can be accurately estimated by its distance to $C$. By utilizing approximate Single Source Shortest Path (SSSP) algorithms, these pseudo-centers can be found significantly faster than exact methods.

Lower Bounds and Hardness Results

To demonstrate the optimality of these algorithms, the authors establish tight lower bounds using reductions from 2-party communication complexity. By reducing hard problems like Tribes, Orthogonal Vectors (OV), and Hitting Set Existence (HSE) to graph problems in the CONGEST model, they prove that certain approximation ratios are physically impossible to achieve in sublinear time.

Summary of distributed lower bounds for distance parameters.

As shown in the lower bound summary, a clear "barrier" exists at the factor of 2 for weighted and directed graphs. Attempting to achieve a $(2-\epsilon)$-approximation for the weighted radius, for instance, triggers a jump in complexity to $\tilde{\Omega}(n)$ rounds. This confirms that the $(2+\epsilon)$ upper bounds achieved by the pseudo-center method are essentially optimal for these variants.

Bi-chromatic Distance Parameters

A significant contribution of this work is the exploration of bi-chromatic variants, where nodes are colored red or blue and only distances between nodes of different colors are considered. This is highly relevant to computational geometry but was previously unexplored in distributed contexts.

The research reveals that bi-chromatic diameter is fundamentally harder than the standard version. The authors provide a $5/3$-approximation algorithm that runs in $\tilde{O}(\sqrt{n} + D)$ rounds, but they also prove a matching lower bound: any $(5/3 - \epsilon)$-approximation requires $\tilde{\Omega}(n)$ rounds. This sharp threshold at $5/3$ distinguishes bi-chromatic problems from their monochromatic counterparts.

Conclusion

This work provides a near-complete characterization of the trade-offs between approximation quality and time complexity in distributed networks. While it settles many long-standing questions, some gaps remain, such as the approximation of directed diameter in the $[3/2, 2]$ range and the exact complexity of the unweighted radius. Future work may extend these tight characterizations to other models like the Congested Clique or Massively Parallel Computation (MPC).

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 \emph{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 \emph{approximate pseudo-center}, which extends the \emph{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},
}
Figure