Document Open Access Logo

Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs

Authors Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, Yann Vaxès

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.22.pdf
  • Filesize: 493 kB
  • 15 pages

Document Identifiers

Author Details

Jérémie Chalopin
Victor Chepoi
Feodor F. Dragan
Guillaume Ducoffe
Abdulhakeem Mohammed
Yann Vaxès

Cite As Get BibTex

Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, and Yann Vaxès. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.22

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 large-scale 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 polynomial-time, 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 n-vertex 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 graph-parameters 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.

Subject Classification

Keywords
  • Gromov hyperbolicity
  • Graphs
  • Geodesic metric spaces
  • Approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Abu-Ata and F.F. Dragan. Metric tree-like structures in real-world networks: an empirical study. Networks, 67(1):49-68, 2016. Google Scholar
  2. A.B. Adcock, B.D. Sullivan, and M.W. Mahoney. Tree-like structure in large social and information networks. In ICDM, pages 1-10. IEEE Computer Society, 2013. Google Scholar
  3. J.M. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro, and H. Short. Notes on word hyperbolic groups. In E. Ghys, A. Haefliger, and A. Verjovsky, editors, Group Theory from a Geometrical Viewpoint, ICTP Trieste 1990, pages 3-63. World Scientific, 1991. Google Scholar
  4. A.M. Ben-Amram. The Euler path to static level-ancestors. CoRR, abs/0909.1030, 2009. Google Scholar
  5. M.A. Bender and M Farach-Colton. The level ancestor problem simplified. Theor. Comput. Sci., 321(1):5-12, 2004. Google Scholar
  6. M. Borassi, D. Coudert, P. Crescenzi, and A. Marino. On computing the hyperbolicity of real-world graphs. In ESA, volume 9294 of Lecture Notes in Computer Science, pages 215-226. Springer, 2015. Google Scholar
  7. M. Borassi, P. Crescenzi, and M. Habib. Into the square: On the complexity of some quadratic-time solvable problems. Electr. Notes Theor. Comput. Sci., 322:51-67, 2016. Google Scholar
  8. B.H. Bowditch. Notes on Gromov’s hyperbolicity criterion for path-metric spaces. In E. Ghys, A. Haefliger, and A. Verjovsky, editors, Group Theory from a Geometrical Viewpoint, ICTP Trieste 1990, pages 64-167. World Scientific, 1991. Google Scholar
  9. M.R. Bridson and A. Haefliger. Metric Spaces of Non-Positive Curvature, volume 319 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 1999. Google Scholar
  10. J. Chalopin, V. Chepoi, F.F. Dragan, G. Ducoffe, A. Mohammed, and Y. Vaxès. Fast approximation and exact computation of negative curvature parameters of graphs. CoRR, abs/1803.06324, 2018. Google Scholar
  11. J. Chalopin, V. Chepoi, P. Papasoglu, and T. Pecatte. Cop and robber game and hyperbolicity. SIAM J. Discrete Math., 28(4):1987-2007, 2014. Google Scholar
  12. V. Chepoi, F.F. Dragan, B. Estellon, M. Habib, and Y. Vaxès. Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs. In Symposium on Computational Geometry, pages 59-68. ACM, 2008. Google Scholar
  13. V. Chepoi, F.F. Dragan, B. Estellon, M. Habib, Y. Vaxès, and Yang Xiang. Additive spanners and distance and routing labeling schemes for hyperbolic graphs. Algorithmica, 62(3-4):713-732, 2012. Google Scholar
  14. V. Chepoi, F.F. Dragan, and Y. Vaxès. Core congestion is inherent in hyperbolic networks. In SODA, pages 2264-2279. SIAM, 2017. Google Scholar
  15. V. Chepoi and B. Estellon. Packing and covering δ-hyperbolic spaces by balls. In APPROX-RANDOM, volume 4627 of Lecture Notes in Computer Science, pages 59-73. Springer, 2007. Google Scholar
  16. N. Cohen, D. Coudert, and A. Lancin. On computing the Gromov hyperbolicity. ACM Journal of Experimental Algorithmics, 20:1.6:1-1.6:18, 2015. Google Scholar
  17. D. Coudert and G. Ducoffe. Recognition of C₄-free and 1/2-hyperbolic graphs. SIAM J. Discrete Math., 28(3):1601-1617, 2014. Google Scholar
  18. D. Coudert, G. Ducoffe, and A. Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. In SODA, pages 2765-2784. SIAM, 2018. Google Scholar
  19. B. DasGupta, M. Karpinski, N. Mobasheri, and F. Yahyanejad. Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications. Algorithmica, 80(2):772-800, 2018. Google Scholar
  20. T. Delzant and M. Gromov. Courbure mésoscopique et théorie de la toute petite simplification. J. Topol., 1:804-836, 2008. Google Scholar
  21. R. Duan. Approximation algorithms for the Gromov hyperbolicity of discrete metric spaces. In LATIN, volume 8392 of Lecture Notes in Computer Science, pages 285-293. Springer, 2014. Google Scholar
  22. K. Edwards, W.S. Kennedy, and I. Saniee. Fast approximation algorithms for p-centers in large δ-hyperbolic graphs. In WAW, volume 10088 of Lecture Notes in Computer Science, pages 60-73, 2016. Google Scholar
  23. T. Fluschnik, C. Komusiewicz, G.B. Mertzios, A. Nichterlein, R. Niedermeier, and N. Talmon. When can graph hyperbolicity be computed in linear time? In WADS, volume 10389 of Lecture Notes in Computer Science, pages 397-408. Springer, 2017. Google Scholar
  24. H. Fournier, A. Ismail, and A. Vigneron. Computing the Gromov hyperbolicity of a discrete metric space. Inf. Process. Lett., 115(6-8):576-579, 2015. Google Scholar
  25. E. Ghys and P. de la Harpe (eds). Les groupes hyperboliques d'après M. Gromov, volume 83 of Progress in Mathematics. Birkhäuser, 1990. Google Scholar
  26. M. Gromov. Hyperbolic groups. In S. Gersten, editor, Essays in Group Theory, volume 8 of Math. Sci. Res. Inst. Publ., pages 75-263. Springer, New York, 1987. Google Scholar
  27. M.F. Hagen. Weak hyperbolicity of cube complexes and quasi-arboreal groups. J. Topology, 7(2):385-418, 2014. Google Scholar
  28. W.S. Kennedy, I. Saniee, and O. Narayan. On the hyperbolicity of large-scale networks and its estimation. In BigData, pages 3344-3351. IEEE, 2016. Google Scholar
  29. O. Narayan and I. Saniee. Large-scale curvature of networks. Phys. Rev. E, 84:066108, 2011. Google Scholar
  30. P. Papasoglu. An algorithm detecting hyperbolicity. In Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994), volume 25 of DIMACS - Series in Discrete Mathematics and Theoretical Computer Science, pages 193-200. 1996. Google Scholar
  31. N. Polat. On infinite bridged graphs and strongly dismantlable graphs. Discrete Mathematics, 211:153-166, 2000. Google Scholar
  32. Y. Shavitt and T. Tankel. Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEE/ACM Trans. Netw., 16(1):25-36, 2008. Google Scholar
  33. M. Soto. Quelques propriétés topologiques des graphes et applications à Internet et aux réseaux. PhD thesis, Université Paris Diderot, 2011. Google Scholar
  34. K. Verbeek and S. Suri. Metric embedding, hyperbolic space, and social networks. In Symposium on Computational Geometry, pages 501-510. ACM, 2014. Google Scholar
  35. H. Yu. An improved combinatorial algorithm for boolean matrix multiplication. In ICALP(1), volume 9134 of Lecture Notes in Computer Science, pages 1094-1105. Springer, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact