Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio

2020/08/26 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.2008.11315

Abstract

We show, assuming the Strong Exponential Time Hypothesis, that for every ε > 0, approximating directed Diameter on m-arc graphs within ratio 7/4 - ε requires m^{4/3 - o(1)} time. Our construction uses nonnegative edge weights but even holds for sparse digraphs, i.e., for which the number of vertices n and the number of arcs m satisfy m = n log^O(1) n. This is the first result that conditionally rules out a near-linear time 5/3-approximation for Diameter.

Related

• 4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n^4/3
• Hardness of Approximate Diameter: Now for Undirected Graphs
• Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
• Approximating the diameter of a graph
• On Diameter Approximation in Directed Graphs