2021/01/07 by Bonnet, Édouard
#05C85 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2101.02312
We show, assuming the Strong Exponential Time Hypothesis, that for every ε > 0, approximating undirected unweighted Diameter on n-vertex n1+o(1)-edge graphs within ratio 7/4 - ε requires n4/3 - o(1) time. This is the first result that conditionally rules out a near-linear time 5/3-approximation for undirected Diameter.