# Better Approximation Algorithms for the Graph Diameter

## Author(s): Chechik, Shiri; Larkin, Daniel H; Roditty, Liam; Schoenebeck, Grant; Tarjan, Robert E; et al

DownloadTo refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr1kk01`

Abstract: | 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 O˜ n 2 + m √ n time an estimate D˜ for the diameter D in directed graphs with nonnegative edge weights, such that b2/3 · Dc−(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 O˜ (m √ n). Roditty and Vassilevska W. also showed that unless the Strong Exponential Time Hypothesis fails, no O n 2−ε 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˜ m 3/2 time, and one running in O˜ mn 2/3 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 O˜ mn1−ε 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 n 2−δ 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 O˜ (m √ n) time, one can compute for each v ∈ V in an undirected graph, an estimate e (v) for the eccentricity (v) such that max {R, 2/3 · (v)} ≤ e (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 0 (v) with 3/5 · (v) ≤ 0 (v) ≤ |

Publication Date: | 2014 |

Citation: | Chechik, Shiri, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert E. Tarjan, and Virginia Vassilevska Williams. "Better Approximation Algorithms for the Graph Diameter." In ACM-SIAM Symposium on Discrete Algorithms (2014): pp. 1041-1052. doi:10.1137/1.9781611973402.78 |

DOI: | 10.1137/1.9781611973402.78 |

Pages: | 1041 - 1052 |

Type of Material: | Conference Article |

Journal/Proceeding Title: | ACM-SIAM Symposium on Discrete Algorithms |

Version: | Author's manuscript |

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.