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

Abstract

We show, assuming the Strong Exponential Time Hypothesis, that for every $\epsilon >0$, approximating directed Diameter on $m$-arc graphs within ratio $7/4-\epsilon$ 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.

arXiv comment13 pages, 4 figures, expanded introduction and discussion on follow-up works