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

International audienceWe 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 non-negative 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). This is the first result that conditionally rules out a near-linear time 5/3-approximation for a variant of Diameter