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

01/07/2021

∙

by   Édouard Bonnet, et al.

∙

0

∙

share

We show, assuming the Strong Exponential Time Hypothesis, that for every ε > 0, approximating undirected unweighted Diameter on n-vertex n^1+o(1)-edge graphs within ratio 7/4 - ε requires m^4/3 - o(1) time. This is the first result that conditionally rules out a near-linear time 5/3-approximation for undirected Diameter.