4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n 4/3
Édouard Bonnet · ACM Transactions on Algorithms · 2022
We show, assuming the Strong Exponential Time Hypothesis, that for every ε > 0, approximating undirected unweighted Diameter on n -vertex m -edge graphs within ratio 7/4 - ε requires m 4/3 - o (1) time, even when m = Õ( n ). This is the first result that conditionally rules out a near-linear time 5/3-approximation for undirected Diameter .