Better Approximation Algorithms for the Graph Diameter

Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert E. Tarjan, Virginia Vassilevska Williams


The diameter is a fundamental graph parameter and its computation is necessary in many applications. The fastest known way to compute the diameter exactly is to solve the All-Pairs Shortest Paths (APSP) problem.

In the absence of fast algorithms, attempts were made to seek fast algorithms that approximate the diameter. In a seminal result Aingworth, Chekuri, Indyk and Motwani [SODA'96 and SICOMP'99] designed an algorithm that computes in $\OTilde{n^2+m\sqrt n}$ time an estimate D* for the diameter D in directed graphs with nonnegative edge weights, such that ⌊⅔ · D⌋ – (M – 1) ≤ D* ≤ D, where M is the maximum edge weight in the graph. In recent work, Roditty and Vassilevska W. [STOC 13] gave a Las Vegas algorithm that has the same approximation guarantee but improves the (expected) runtime to $\OTilde{m\sqrt n}$. Roditty and Vassilevska W. also showed that unless the Strong Exponential Time Hypothesis fails, no O(n2−) time algorithm for sparse unweighted undirected graphs can achieve an approximation ratio better than 3/2. Thus their algorithm is essentially tight for sparse unweighted graphs. For weighted graphs however, the approximation guarantee can be meaningless, as M can be arbitrarily large.

In this paper we exhibit two algorithms that achieve a genuine 3/2-approximation for the diameter, one running in O(m3/2) time, and one running in O(mnn3/2) time. Furthermore, our algorithms are deterministic, and thus we present the first deterministic (2 – )-approximation algorithm for the diameter that takes subquadratic time in sparse graphs.

In addition, we address the question of obtaining an additive c-approximation for the diameter, i.e. an estimate D* such that D – c ≤ D* ≤ D. An extremely simple $\OTilde{m\sqrt n}$ time algorithm achieves an additive n-approximation; no better results are known. We show that for any > 0, getting an additive n-approximation algorithm for the diameter running in O (n2−δ) time for any δ > 2 would falsify the Strong Exponential Time Hypothesis. Thus the simple algorithm is probably essentially tight for sparse graphs, and moreover, obtaining a subquadratic time additive c-approximation for any constant c is unlikely.

Finally, we consider the problem of computing the eccentricities of all vertices in an undirected graph, i.e. the largest distance from each vertex. Roditty and Vassilevska W. [STOC 13] show that in $\OTilde{m\sqrt n}$ time, one can compute for each vV in an undirected graph, an estimate ∊(v) for the eccentricity ∊(v) such that max {R, 2/3 · ∊(v)} ≤ ∊(v) ≤ min {D, 3/2 · ∊(v)} where R = minv ∊(v) is the radius of the graph. Here we improve the approximation guarantee by showing that a variant of the same algorithm can achieve estimates ∊(v) with 5/3 · ∊(v) ≤ ∊′(v) ≤ ∊(v).


 [ back to Grant's homepage]