Towards tight approximation bounds for graph diameter and eccentricities

DOI10.1145/3188745.3188950zbMATH Open1427.68225arXiv1808.08494OpenAlexW2803761918MaRDI QIDQ5230295

Author name not available (Why is that?)

Publication date: 22 August 2019

Published in: (Search for Journal in Brave)

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 approximated. Chechik et al. showed that the diameter can be approximated within a multiplicative factor of $3/2$ in $ildeO(m^{3/2})$ time. Furthermore, Roditty and Vassilevska W. showed that unless the Strong Exponential Time Hypothesis (SETH) fails, no $O(n^{2-epsilon})$ time algorithm 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-epsilon})$ time algorithm can achieve an approximation factor better than $5/3$. Another fundamental set of graph parameters are the Eccentricities. The Eccentricity of a vertex $v$ is the distance between $v$ and the farthest vertex from $v$. Chechik et al. showed that the Eccentricities of all vertices can be approximated within a factor of $5/3$ in $ildeO(m^{3/2})$ time and Abboud et al. showed that no $O(n^{2-epsilon})$ algorithm can achieve better than $5/3$ approximation in sparse graphs. We show that the runtime of the $5/3$ approximation algorithm is also optimal under SETH. We also show that no near-linear time algorithm can achieve a better than $2$ approximation for the Eccentricities and that this is essentially tight: we give an algorithm that approximates Eccentricities within a $2+delta$ factor in $ildeO(m/delta)$ time for any $0<delta<1$. This beats all Eccentricity algorithms in Cairo et al.

Full work available at URL: https://arxiv.org/abs/1808.08494

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Towards tight approximation bounds for graph diameter and eccentricities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230295)