Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

\(\delta \)-Hyperbolic graphs, originally conceived by Gromov (Essays in group theory. 1987), occur often in many network applications; for fixed \(\delta \), such graphs are simply called hyperbolic graphs and include non-trivial interesting classes of “non-expander” graphs. The main motivation of this paper is to investigate the effect of the hyperbolicity measure \(\delta \) on expansion and cut-size bounds on graphs (here \(\delta \) need not be a constant), and the asymptotic ranges of \(\delta \) for which these results may provide improved approximation algorithms for related combinatorial problems. To this effect, we provide constructive bounds on node expansions for \(\delta \)-hyperbolic graphs as a function of \(\delta \), and show that many witnesses (subsets of nodes) for such expansions can be computed efficiently even if the witnesses are required to be nested or sufficiently distinct from each other. To the best of our knowledge, these are the first such constructive bounds proven. We also show how to find a large family of s–t cuts with relatively small number of cut-edges when s and t are sufficiently far apart. We then provide algorithmic consequences of these bounds and their related proof techniques for two problems for \(\delta \)-hyperbolic graphs (where \(\delta \) is a function f of the number of nodes, the exact nature of growth of f being dependent on the particular problem considered).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. This is in contrast to many research works in this area where one studies the properties of \(\delta \)-hyperbolic graphs assuming \(\delta \) to be fixed.

  2. We will later need to vary the value of \(\alpha \) in our analysis.

  3. Note that if there is no path between nodes p and q in \(G_{-\mathcal {C}}\) then \(\mathrm {dist}_{G_{-\mathcal {C}}}(p,q)=\infty \) and \(\mathcal {B}_{G_{-\mathcal {C}}}\left( p,{\mathrm {dist}_{G_{-\mathcal {C}}}(p,q)}/{2}\right) \) and \(\mathcal {B}_{G_{-\mathcal {C}}}\left( q,{\mathrm {dist}_{G_{-\mathcal {C}}}(p,q)}/{2}\right) \) contain all the nodes reachable from p and q, respectively, in \(G_{-\mathcal {C}}\).

References

  1. Albert, R., DasGupta, B., Mobasheri, N.: Topological implications of negative curvature for biological and social networks. Phys. Rev. E 89(3), 032811 (2014)

    Article  Google Scholar 

  2. Ariaei, F., Lou, M., Jonckheere, E., Krishnamachari, B., Zuniga, M.: Curvature of sensor network: clustering coefficient. EURASIP J. Wirel. Commun. Netw. 2008, 213185 (2009)

  3. Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for unique games and related problems. In: 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 563–572 (2010)

  4. Assadi, S., Emamjomeh-Zadeh, E., Norouzi-Fard, A., Yazdanbod, S., Zarrabi-Zadeh, H.: The minimum vulnerability problem. Algorithmica 70, 718–731 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bansal, N., Feige, U., Krauthgamer, R., Makarychev, K., Nagarajan, V., Naor, J., Schwartz, R.: Min–max graph partitioning and small set expansion. In: 52nd Annual IEEE Symposium on Foundations of Computer Science, pp. 17–26 (2011)

  6. Benjamini, I.: Expanders are not hyperbolic. Isr. J. Math. 108, 33–36 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  7. Benjamini, I., Hoppen, C., Ofek, E., Pralat, P., Wormald, N.: Geodesics and almost geodesic cycles in random regular graphs. J. Graph Theory 66, 115–136 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  8. Benjamini, I., Schramm, O.: Finite transitive graph embedding into a hyperbolic metric space must stretch or squeeze. In: Klartag, B., Mendelson, S., Milman V.D. (eds.) Geometric Aspects of Functional Analysis, pp. 123–126. Springer, Berlin (2012)

  9. Bodlaender, H.L.: Dynamic programming on graphs with bounded treewidth. In: Lepistö, T., Salomaa, A. (eds.) Lecture Notes in Computer Science, vol. 317, pp. 105–118. Springer, Berlin (1988)

    Google Scholar 

  10. Bridson, M.R., Haefliger, A.: Metric Spaces of Non-positive Curvature. Springer, Berlin (1999)

    Book  MATH  Google Scholar 

  11. Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vaxès, Y.: Diameters, centers, and approximating trees of \(\delta \)-hyperbolic geodesic spaces and graphs. In: Proceedings of the 24th Annual Symposium on Computational Geometry, pp. 59–68 (2008)

  12. Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vaxès, Y., Xiang, Y.: Additive spanners and distance and routing labeling schemes for \(\delta \)-hyperbolic graphs. Algorithmica 62(3–4), 713–732 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  13. Chepoi, V., Estellon, B.: Packing and covering \(\delta \)-hyperbolic spaces by balls. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) Lecture Notes in Computer Science, vol. 4627, pp. 59–73. Springer, Berlin (2007)

    Google Scholar 

  14. Chung, F.R.K.: Spectral graph theory. In: CBMS Regional Conference Series in Mathematics, vol. 92 (1997)

  15. de Montgolfier, F., Soto, M., Viennot, L.:. Treewidth and hyperbolicity of the internet. In: Proceedings of the 10th IEEE International Symposium on Networking Computing and Applications, pp. 25–32 (2011)

  16. Eppstein, D., Goodrich, M.T.: Succinct greedy geometric routing using hyperbolic geometry. IEEE Trans. Comput. 60(11), 1571–1580 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  17. Even, G., Kortsarz, G., Slany, W.: On network design problems: fixed cost flows and the covering Steiner problem. ACM Trans. Algorithms 1(1), 74–101 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  18. Fournier, H., Ismail, A., Vigneron, A.: Computing the Gromov hyperbolicity of a discrete metric space. Inf. Process. Lett. 115(6–8), 576–579 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  19. Gandhi, R., Kortsarz, G.: On edge expansion problems and the small set expansion conjecture. Discr. Appl. Math. 194, 93–101 (2015)

    Article  MATH  Google Scholar 

  20. Gavoille, C., Ly, O.: Distance labeling in hyperbolic graphs. In: Deng, X., Du, D.-Z. (eds.) Lecture Notes in Computer Science, vol. 3827, pp. 1071–1079. Springer, Berlin (2005)

    Google Scholar 

  21. Gromov, M.: Hyperbolic groups. In: Gersten, S.M. (ed.) Essays in Group Theory, pp. 75–263. Springer, New York (1987)

  22. Jonckheere, E., Lohsoonthorn, P., Bonahon, F.: Scaled Gromov hyperbolic graphs. J. Graph Theory 57(2), 157–180 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  23. Jonckheere, E., Lohsoonthorn, P., Ariaei, F.: Scaled Gromov four-point condition for network graph curvature computation. Internet Math. 7(3), 137–177 (2011)

    Article  MathSciNet  Google Scholar 

  24. Jonckheere, E., Lou, M., Bonahon, F., Baryshnikov, Y.: Euclidean versus hyperbolic congestion in idealized versus experimental networks. Internet Math. 7(1), 1–27 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  25. Kleinberg, R.: Geographic routing using hyperbolic space. In: 26th IEEE International Conference on Computer Communications, pp. 1902–1909 (2007)

  26. Louis, A., Raghavendra, P., Vempala, S.: The complexity of approximating vertex expansion. In: 54th IEEE Annual Symposium on Foundations of Computer Science, vol. 360–369 (2013)

  27. Malyshev, A.: Expanders are order diameter non-hyperbolic. arXiv:1501.07904 (2015)

  28. Narayan, O., Saniee, I., Tucci, G.H.: Lack of hyperbolicity in asymptotic Erdös–Renyi sparse random graphs. Internet Math. 11(3), 277–288 (2015)

    Article  MathSciNet  Google Scholar 

  29. Omran, M.T., Sack, J.-R., Zarrabi-Zadeh, H.: Finding paths with minimum shared edges. J. Comb. Optim. 26(4), 709–722 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  30. Papadopoulos, F., Krioukov, D., Boguna, M., Vahdat, A.: Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In: IEEE INFOCOM, pp. 1–9 (2010)

  31. Raghavendra, P., Steurer, D.: Graph expansion and the unique games conjecture. In: 45th ACM Symposium on Theory of Computing, pp. 755–764 (2010)

  32. Raghavendra, P., Steurer, D., Tetali, P.: Approximations for the isoperimetric and spectral profile of graphs and related parameters. In: 45th ACM Symposium on Theory of Computing, pp. 631–640 (2010)

  33. Raghavendra, P., Steurer, D., Tulsiani, M.: Reductions between expansion problems. In: IEEE Conference on Computational Complexity, pp. 64–73 (2012)

  34. Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest. J. Comb. Theory Ser. B 35(1), 39–61 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  35. Vazirani, V.: Approximation Algorithms. Springer, Berlin (2001)

    MATH  Google Scholar 

  36. Wang, J., Yang, M., Yang, B., Zheng, S.Q.: Dual-homing based scalable partial multicast protection. IEEE Trans. Comput. 55(9), 1130–1141 (2006)

    Article  Google Scholar 

  37. Yang, B., Yang, M., Wang, J., Zheng, S.Q.: Minimum cost paths subject to minimum vulnerability for reliable communications. In: 8th International Symposium on Parallel Architectures, Algorithms and Networks, pp. 334–339 (2005)

  38. Zheng, S.Q., Wang, J., Yang, B., Yang, M.: Minimum-cost multiple paths subject to minimum link and node sharing in a network. IEEE/ACM Trans. Netw. 18(5), 1436–1449 (2010)

    Article  Google Scholar 

Download references

Acknowledgements

B. DasGupta, N. Mobasheri and F. Yahyanejad thankfully acknowledge supported from NSF Grant IIS-1160995 for this research. M. Karpinski was supported in part by DFG Grants. The problem of investigating expansion properties of \(\delta \)-hyperbolic graphs was raised originally to some of the authors by A. Wigderson.

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Illinois at Chicago, Chicago, IL, 60607, USA

    Bhaskar Das Gupta, Nasim Mobasheri & Farzane Yahyanejad

  2. Department of Computer Science, University of Bonn, Bonn, 53113, Germany

    Marek Karpinski

Authors
  1. Bhaskar Das Gupta
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marek Karpinski
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nasim Mobasheri
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Farzane Yahyanejad
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bhaskar Das Gupta.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Das Gupta, B., Karpinski, M., Mobasheri, N. et al. Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications. Algorithmica 80, 772–800 (2018). https://doi.org/10.1007/s00453-017-0291-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-017-0291-7

Keywords

Mathematics Subject Classification

Search

Navigation