A note on hardness of diameter approximation

作者：Bringmann Karl; Krinninger Sebastian^*

来源：Information Processing Letters, 2018, 133: 10-15.

DOI：10.1016/j.ipl.2017.12.010

• Distributed computing
• Lower bounds
• Hardness in P
• Graph algorithms

We revisit the hardness of approximating the diameter of a network. In the CONGEST model of distributed computing, (Omega) over tilde (n) rounds are necessary to compute the diameter (Frischknecht et al., 2012 [2]), where (Omega) over tilde(center dot) hides polylogarithmic factors. Abboud et al. (2016) [3] extended this result to sparse graphs and, at a more fine-grained level, showed that, for any integer 1 <= l <= polylog(n), distinguishing between networks of diameter 4l + 2 and 6l + 1 requires (Omega) over tilde (n) rounds. We slightly tighten this result by showing that even distinguishing between diameter 2l + 1 and 3l + 1 requires (Omega) over tilde (n) rounds. The reduction of Abboud et al. is inspired by recent conditional lower bounds in the RAM model, where the orthogonal vectors problem plays a pivotal role. In our new lower bound, we make the connection to orthogonal vectors explicit, leading to a conceptually more streamlined exposition.

• 出版日期2018-5