23.02.2016

δ-hyperbolic graphs, originally conceived by Gromov in 1987, include non-trivial interesting classes of “non-expander” graphs; for fixed δ, such graphs are simply called hyperbolic graphs. Our goal in this paper is to study the effect of the hyperbolicity measure δ on expansion and cut-size bounds on graphs (here δ need not be a constant, i.e., the graph is not necessarily hyperbolic), and investigate up to what values of δ these results could provide improved approximation algorithms for related combinatorial problems. To this effect, we provide the following results.

• We provide constructive bounds on node expansions and cut-sizes for δ-hyperbolic graphs as a function of δ, and show that witnesses for such non-expansion or cut-size can be computed efficiently in polynomial time. 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 small number of cut-edges when s and t are sufficiently far apart.
• We also provide the following algorithmic consequences of these bounds and their related proof techniques for a few problems related to cuts and paths for δ-hyperbolic graphs (where δ need not necessarily a constant but may be a function f of the number of nodes, the exact nature of growth of f depends on the problem considered):
– We provide improved approximation algorithms for minimizing the number of bottleneck edges that arises in network design applications. En route, we also formulate the hitting set problem of size-constrained cuts and show a connection between approximability issues of these two problems.
– We provide a polynomial-time solution for a type of small-set expansion problem that arises in the investigation of unique games conjecture.