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,
-
a (6/11 + eps)-approximation requires Omega(n^{1/6}/log n) rounds,
-
a (4/7 + eps)-approximation requires Omega(n^{1/4}/log n) rounds,
-
and a (3/5 + eps)-approximation requires Omega(n^{1/3}/log n) rounds.
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.