Near Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks
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$
DISC