30.10.2015

Gromov-hyperbolic graphs (or, hyperbolic graphs for short) are a non-trivial interesting classes of non-expander graphs. Originally conceived by Gromov in 1987 in a different con- text while studying fundamental groups of a Riemann surface, the hyper bolicity measure for graphs has recently been a quite popular measure in the network science community in quantifying curvature and closeness to a tree topology for a given network, and ma ny real-world networks have been empirically observed to be hyperbolic.
In this paper, we provide constructive non-trivial bounds on node expansions and cut- sizes for hyperbolic graphs, and show that witnesses for such non- expansion or cut-size can in fact be computed efficiently in polynomial time. We also provide so me algorithmic consequences of these bounds and their related proof techniques for a few pro blems related to cuts and paths for hyperbolic graphs, such as the existence of a large family of s-t cuts with small number of cut-edges for when s and t are at least logarithmically far apart, efficient approximat ion of hitting sets of size-constrained cuts, and a polynomial-time solution for a type of small-set expansion problem originally proposed by Arora, Barak and Steurer.