Tight conditional lower bounds for approximating diameter in directed graphs

Among the most fundamental graph parameters is the Diameter, the largest distance between any pair of vertices in a graph. Computing the Diameter of a graph with m edges requires m2−o(1) time under the Strong Exponential Time Hypothesis (SETH), which can be prohibitive for very large graphs, so efficient approximation algorithms for Diameter are desired.