Towards Tight Approximation Bounds for Graph Diameter and Eccentricities

Abstract

Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter exactly. Thus, much research has been devoted to how fast this parameter can be {\em approximated}. Chechik et al.\ [SODA 2014] showed that the diameter can be approximated within a multiplicative factor of $3/2$ in $\tO(m^{3/2})$ time. Roditty and Vassilevska W.\ [STOC 13] showed that unless the Strong Exponential Time Hypothesis (SETH) fails, no $O(n^{2-\eps})$ time algorithm for $\eps>0$ can achieve an approximation factor better than $3/2$ in sparse graphs. Thus the above algorithm is essentially optimal for sparse graphs for approximation factors less than $3/2$. It was, however, completely plausible that a $3/2$-approximation is possible in linear time.

In this work we conditionally rule out such a possibility by showing that unless SETH fails no $O(m^{3/2-\eps})$ time algorithm can achieve an approximation factor better than $5/3$. We provide similarly tight results for other distance-related parameters, also providing new algorithms.

To establish the our lower bounds we study the $S$-$T$ Diameter problem: Given a graph and two subsets $S$ and $T$ of vertices, output the largest distance between a vertex in $S$ and a vertex in $T$. We give new algorithms and show tight lower bounds that serve as a starting point for all other hardness results. In this talk I will explain the lower bound constructions for $S$-$T$ Diameter and will outline how one can extend them for Diameter as well.

Joint work with Arturs Backurs, Nicole Wein, Liam Roditty and Gilad Segal. To appear in STOC 2018.