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 m 2− 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. There is a folklore algorithm that gives a 2-approximation for Diameter in Õ( m ) time (where Õ notation suppresses logarithmic factors). Additionally, a line of work [SODA’96, STOC’13, SODA’14] concludes with a 3/2-approximation algorithm for Diameter in weighted directed graphs that runs in Õ( m 3/2 ) time. For directed graphs, these are the only known approximation algorithms for Diameter. The 3/2-approximation algorithm is known to be tight under SETH: Roditty and Vassilevska W. [STOC’13] proved that under SETH any 3/2−ε approximation algorithm for Diameter in undirected unweighted graphs requires m 2− o (1) time, and then Backurs, Roditty, Segal, Vassilevska W., and Wein [STOC’18] and the follow-up work of Li proved that under SETH any 5/3−ε approximation algorithm for Diameter in undirected unweighted graphs requires m 3/2− o (1) time. Whether or not the folklore 2-approximation algorithm is tight, however, is unknown, and has been explicitly posed as an open problem in numerous papers. Towards this question, Bonnet recently proved that under SETH, any 7/4−ε approximation requires m 4/3− o (1) , only for directed weighted graphs. We completely resolve this question for directed graphs by proving that the folklore 2-approximation algorithm is conditionally optimal. In doing so, we obtain a series of conditional lower bounds that together with prior work, give a complete time-accuracy trade-off that is tight with the three known algorithms for directed graphs. Specifically, we prove that under SETH for any δ>0, a (2 k −1/ k −δ)-approximation algorithm for Diameter on directed unweighted graphs requires m k / k −1− o (1) time.

Authors

• Mina Dalirrooyfard
• Nicole Wein

Keywords

• fine-grained complexity
• graph algorithms
• graph diameter