Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH)
Ray Li · 2021
We prove several tight results on the fine-grained complexity of approximating the diameter of a graph. First, we prove that, for any ε>0, assuming the Strong Exponential Time Hypothesis (SETH), there are no near-linear time 2−ε-approximation algorithms for the Diameter of a sparse directed graph, even in unweighted graphs. This result shows that a simple near-linear time 2-approximation algorithm for Diameter is optimal under SETH, answering a question from a survey of Rubinstein and Vassilevska-Williams (SIGACT ’19) for the case of directed graphs.