Near-linear time for undirected graphs

4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time $n^{4/3}$

Approximating undirected unweighted diameter on graphs within ratio requires time.We show, assuming the strong exponential time hypothesis, that for every approximating undirected unweighted diameter on graphs within ratio requires time.This is the first result that conditionally rules out a near-linear time for undirected diameter.