New Bounds for Approximating Extremal Distances in Undirected Graphs

International audienceWe provide new bounds for the approximation of extremal distances (the diameter, the radius, and the eccentricities of all nodes) of an undirected graph with n nodes and m edges. First, we show under the Strong Exponential Time Hypothesis (SETH) of Impagliazzo, Paturi and Zane [JCSS01] that it is impossible to get a (3/2−ε)-approximation of the diameter or a (5/3 − ε)-approximation of all the eccentricities in O(m 2−δ) time for any ε, δ > 0, even allowing for a constant additive term in the approximation. Second, we present an algorithmic scheme that gives a (2 − 1/2 k)-approximation of the diameter and the radius and a (3 − 4/(2 k + 1))-approximation of all eccentricities in O(mn 1 k+1) expected time for any k ≥ 0. For k ≥ 2, this gives a family of previously unknown bounds, and approaches near-linear running time as k grows. Third, we observe a connection between the approximation of the diameter and the h-dominating sets, which are subsets of nodes at distance ≤ h from every other node. We give bounds for the size of these sets, related with the diameter