We develop a new technique for constructing sparse graphs that allow us to
prove near-linear lower bounds on the round complexity of computing distances
in the CONGEST model. Specifically, we show an $\widetilde{\Omega}(n)$ lower
bound for computing the diameter in sparse networks, which was previously known
only for dense networks [Frishknecht et al., SODA 2012]. In fact, we can even
modify our construction to obtain graphs with constant degree, using a simple
but powerful degree-reduction technique which we define.
Moreover, our technique allows us to show $\widetilde{\Omega}(n)$ lower
bounds for computing $(\frac{3}{2}-\varepsilon)$-approximations of the diameter
or the radius, and for computing a $(\frac{5}{3}-\varepsilon)$-approximation of
all eccentricities. For radius, we are unaware of any previous lower bounds.
For diameter, these greatly improve upon previous lower bounds and are tight up
to polylogarithmic factors [Frishknecht et al., SODA 2012], and for
eccentricities the improvement is both in the lower bound and in the
approximation factor [Holzer and Wattenhofer, PODC 2012].
Interestingly, our technique also allows showing an almost-linear lower bound
for the verification of $(\alpha,\beta)$-spanners, for $\alpha < \beta+1$.

本篇研究提出了一种构建稀疏图的新技术，能够证明计算 CONGEST 模型中距离的轮廓复杂度的近似线性下界，它能够计算直径、半径和所有偏心距的近似值，并且这些下界能够比以前的下界有所改善。