Hardness of Approximate Diameter: Now for Undirected Graphs
Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2 approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near linear time. A series of papers on fine grained complexity have led to strong hardness results for diameter in directed graphs, culminating in a recent tradeoff curve independently discovered by [Li, STOC'21] and [Dalirrooyfard and Wein, STOC'21] showing that under the Strong Exponential Time Hypothesis (SETH) for any integer k 2 and d 0, a 2 1 k d approximation for diameter in directed m edge graphs requires mn1+1/(k 1) o(1) time. In particular, the simple linear time 2 approximation algorithm is optimal for directed graphs. In this paper we prove that the same tradeoff lower bound curve is possible for undirected graphs as well, extending results of [Roditty and Vassilevska W. STOC'13] [Li'20] and [Bonnet, ICALP'21] who proved the first few cases of the curve, k 2, 3 and 4, respectively. Our result shows in particular that the simple linear time 2 approximation algorithm is also optimal for undirected graphs. To obtain our result we develop new tools for fine grained reductions that could be useful for proving SETH based hardness for other problems in undirected graphs related to distance computation. *Department of Electrical Engineering and Computer Science and CSAIL, MIT. minad@mit.edu. Research supported by the National Science Foundation (NSF) under NSF CAREER Award 1651838 Department of Computer Science, Stanford University. rayyli@cs.stanford.edu. Research supported by the National Science Foundation (NSF) under Grant No. DGE 1656518 and by Jacob Fox's Packard Fellowship. Department of Electrical Engineering and Computer Science and CSAIL, MIT. virgi@mit.edu. Supported by NSF CAREER Award 1651838, NSF Grants CCF 1528078, CCF 1514339 and CCF 1909429, BSF Grant BSF:2012338, a Google Research Fellowship and a Sloan Research Fellowship. ar X iv :2 10 6. 06 02 6v 1 cs .C C 1 0 Ju n 20 21
ArXiv