The diameter and the radius of a graph are fundamental topological parameters that have many important practical applications in real world networks. The fastest combinatorial algorithm for both parameters works by solving the all-pairs shortest paths problem (APSP) and has a running time of O(mn) in m-edge, n-node graphs. In a seminal paper, Aingworth, Chekuri, Indyk and Motwani [SODA'96 and SICOMP'99] presented an algorithm that computes in O(m √ n + n 2 ) time an estimateD for the diameter D, such that 2/3D ≤D ≤ D. Their paper spawned a long line of research on approximate APSP. For the specific problem of diameter approximation, however, no improvement has been achieved in over 15 years. Our paper presents the first improvement over the diameter approximation algorithm of Aingworth et al. , producing an algorithm with the same estimate but with an expected running time of O(m √ n). We thus show that for all sparse enough graphs, the diameter can be 3/2-approximated in o(n 2 ) time. Our algorithm is obtained using a surprisingly simple method of neighborhood depth estimation that is strong enough to also approximate, in the same running time, the radius and more generally, all of the eccentricities, i.e. for every node the distance to its furthest node. We also provide strong evidence that our diameter approximation result may be hard to improve. We show that if for some constant ε > 0 there is an O(m 2−ε ) time (3/2 − ε)-approximation algorithm for the diameter of undirected unweighted graphs, then there is an O * ((2 − δ) n ) time algorithm for CNF-SAT on n variables for constant δ > 0, and the strong exponential time hypothesis of [Impagliazzo, Paturi, Zane JCSS'01] is false. * Work supported by the Israel Science Foundation (grant no. 822/10). † Partially supported by NSF Grants CCF-0830797 and CCF-1118083 at UC Berkeley, and by NSF Grants IIS-0963478 and IIS-0904325, and an AFOSR MURI Grant, at Stanford University. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Motivated by this negative result, we give several improved diameter approximation algorithms for special cases. We show for instance that for unweighted graphs of constant diameter D not divisible by 3, there is an O(m 2−ε ) time algorithm that gives a (3/2 − ε) approximation for constant ε > 0. This is interesting since the diameter approximation problem is hardest to solve for small D.
An interesting example of such result concerns the diameter: Roditty and Vassilevska W. REF proved that if the diameter of sparse graphs can be computed in truly-subquadratic O(n 2−ε ) time, for any ε > 0, then the Strong Exponential Time Hypothesis (SETH) is false 2 , by reducing SAT to diameter.
Fast approximation algorithms for the diameter and radius of sparse graphs
STOC '13
Mathematics Computer Science