摘要：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 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 = OËO(n). This is the first result that conditionally rules out a near-linear time 5/3-approximation for a variant of Diameter.
