Computing the gromov hyperbolicity of a discrete metric space

H. Fournier, A. Ismail, A. Vigneron
Information Processing Letters, 115(6-8), 576-579, (2015)

Computing the gromov hyperbolicity of a discrete metric space

Keywords

Algorithms design and analysis, Approximation algorithms,Discrete metric space, Hyperbolic space, (max,min) matrix product

Abstract

We give exact and approximation algorithms for computing the Gromov hyperbolicity of an n  -point discrete metric space. We observe that computing the Gromov hyperbolicity from a fixed base-point reduces to a (max,min) matrix product. Hence, using the (max,min) matrix product algorithm by Duan and Pettie, the fixed base-point hyperbolicity can be determined in O(n2.69)O(n2.69) time. It follows that the Gromov hyperbolicity can be computed in O(n3.69)O(n3.69) time, and a 2-approximation can be found in O(n2.69)O(n2.69) time. We also give a (2log2⁡n)(2log2⁡n)-approximation algorithm that runs in O(n2)O(n2) time, based on a tree-metric embedding by Gromov. We also show that hyperbolicity at a fixed base-point cannot be computed in O(n2.05)O(n2.05) time, unless there exists a faster algorithm for (max,min) matrix multiplication than currently known.

Code

DOI: 10.1016/j.ipl.2015.02.002

Sources

Website PDF

See all publications 2015