Department of Computer Science
Chair V

University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2016 Copyright 2016 University of Bonn, Department of Computer Science, Abt. V


Effect of Gromov-Hyperbolicity Parameters on Cuts and Expansions in Graphs and Some Algorithmic Implications
Bhaskar DasGupta, Marek Karpinski, Nasim Mobasheri, Farzaneh Yahyanejad
[Download PostScript] [Download PDF]

δ-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.

Last Change: 02/23/16 at 10:27:52
University of Bonn -> Department of Computer Science -> Chair V