Reduction from CNF-SAT to Approximate Diameter

FROM: CNF-SAT TO: Approximate Diameter

Implications

if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$ for a $({3}/{2} - \epsilon)$-approximation
then: from-time: $O*(({2}-\delta)^n)$ for constant $\delta > {0}$

Year

2013

Reference

L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515–524, 2013.

https://people.csail.mit.edu/virgi/diam.pdf