Reduction from Triangle Collection* to dynamic 4/3-Diameter

FROM: Triangle Collection* TO: dynamic 4/3-Diameter

Implications

assume: SETH or {3}SUM Hypothesis or APSP Hypothesis
then: there exists no incremental (or decremental) algorithm that approximates the diameter of unweighted graph within a factor of ${4}/{3}-\epsilon$ running in amortized time $O(n^{1/{2}-\epsilon'})$ for any $\epsilon,\epsilon' > {0}$. Furthermore, if we allow node insertions in the incremental case the bound is $O(n^{0.{618}-\epsilon'})$

Year

2016

Reference

Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to diameter. arXiv preprint arXiv:1602.06705.

https://arxiv.org/abs/1602.06705