Improved Hardness of Approximation for Distributed Diameter

by Ofer Grossman, Seri Khoury, and Ami Paz

Oded's comments

I was fascinated by the fact that different levels of approximation, let alone in the constant range, seem to require different complexity. I have emphasized this aspect in the original abstract by itemizing the three bounds. Furthermore, a recent result of Ancona et al (2020) gives an O(n^{1/3}+D)-round algorithm that yields a 4/7-approximation.

The original abstract (slightly revised)

We study the problem of approximating the diameter D of an unweighted and undirected n-node graph in the congest model. Through a connection to extremal combinatorics, we show that, for every positive eps,

These lower bounds are robust in the sense that they hold even against algorithms that are allowed to return an additional small additive error. Prior to our work, only lower bounds for (2/3 + eps)-approximation were known [Frischknecht et al. SODA 2012, Abboud et al. DISC 2016]. Furthermore, we prove that distinguishing graphs of diameter 3 from graphs of diameter 5 requires Oemga(n/log n) rounds. This stands in sharp contrast to previous work: while there is an algorithm that returns an estimate in [2/3D,D] in tildeO(sqrt(n)+D) rounds [Holzer et al. DISC 2014], our lower bound implies that any algorithm for returning an estimate in [(2/3+eps)D,D] requires tildeOmega(n) rounds.

Available from LiPICS record of DISC'20

Back to list of Oded's choices.