Reduction from 3-OV to Diameter 3 vs 7

FROM: 3-OV TO: Diameter 3 vs 7

Implications

If: to-time: $O(N^{({3}/{2}-\epsilon)}$ where $N=n^{2} d^{2}$ and $\epsilon > {0}$
Then: from-time: $n^{3-{2}\epsilon} poly(d)$

Year

2018

Reference

Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities.

https://dl.acm.org/doi/pdf/10.1145/3188745.3188950