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

Abstract: We show, assuming the Strong Exponential Time Hypothesis, that for every

v a r e p s i l o n > 0

, approximating directed Diameter on

m

-arc graphs within ratio

7 / 4 - v a r e p s i l o n

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 l o g^{O (1)} n

. This is the first result that conditionally rules out a near-linear time

5 / 3

-approximation for Diameter.

This page was built for publication: Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio