Chalopin, Jérémie ;
Chepoi, Victor ;
Dragan, Feodor F. ;
Ducoffe, Guillaume ;
Mohammed, Abdulhakeem ;
Vaxès, Yann
Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs
Abstract
In this paper, we study Gromov hyperbolicity and related parameters, that represent how close (locally) a metric space is to a tree from a metric point of view. The study of Gromov hyperbolicity for geodesic metric spaces can be reduced to the study of graph hyperbolicity. Our main contribution in this note is a new characterization of hyperbolicity for graphs (and for complete geodesic metric spaces). This characterization has algorithmic implications in the field of largescale network analysis, which was one of our initial motivations. A sharp estimate of graph hyperbolicity is useful, {e.g.}, in embedding an undirected graph into hyperbolic space with minimum distortion [Verbeek and Suri, SoCG'14]. The hyperbolicity of a graph can be computed in polynomialtime, however it is unlikely that it can be done in subcubic time. This makes this parameter difficult to compute or to approximate on large graphs. Using our new characterization of graph hyperbolicity, we provide a simple factor 8 approximation algorithm for computing the hyperbolicity of an nvertex graph G=(V,E) in optimal time O(n^2) (assuming that the input is the distance matrix of the graph). This algorithm leads to constant factor approximations of other graphparameters related to hyperbolicity (thinness, slimness, and insize). We also present the first efficient algorithms for exact computation of these parameters. All of our algorithms can be used to approximate the hyperbolicity of a geodesic metric space.
BibTeX  Entry
@InProceedings{chalopin_et_al:LIPIcs:2018:8735,
author = {J{\'e}r{\'e}mie Chalopin and Victor Chepoi and Feodor F. Dragan and Guillaume Ducoffe and Abdulhakeem Mohammed and Yann Vax{\`e}s},
title = {{Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {22:122:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770668},
ISSN = {18688969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8735},
URN = {urn:nbn:de:0030drops87356},
doi = {10.4230/LIPIcs.SoCG.2018.22},
annote = {Keywords: Gromov hyperbolicity, Graphs, Geodesic metric spaces, Approximation algorithms}
}
08.06.2018
Keywords: 

Gromov hyperbolicity, Graphs, Geodesic metric spaces, Approximation algorithms 
Seminar: 

34th International Symposium on Computational Geometry (SoCG 2018)

Issue date: 

2018 
Date of publication: 

08.06.2018 