  Among the most fundamental graph parameters is the Diameter, the largest
distance between any pair of vertices. 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
$\tilde{O}(m)$ time. Additionally, a line of work concludes with a
$3/2$-approximation algorithm for Diameter in weighted directed graphs that
runs in $\tilde{O}(m^{3/2})$ time. The $3/2$-approximation algorithm is known
to be tight under SETH: Roditty and Vassilevska W. proved that under SETH any
$3/2-\epsilon$ approximation algorithm for Diameter in undirected unweighted
graphs requires $m^{2-o(1)}$ time, and then Backurs, Roditty, Segal,
Vassilevska W., and Wein and the follow-up work of Li proved that under SETH
any $5/3-\epsilon$ 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-\epsilon$ 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 all known algorithms for
directed graphs. Specifically, we prove that under SETH for any $\delta>0$, a
$(\frac{2k-1}{k}-\delta)$-approximation algorithm for Diameter on directed
unweighted graphs requires $m^{\frac{k}{k-1}-o(1)}$ time.
