Department of Computer Science
 
Chair V

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

30.10.2015

Node Expansions and Cuts in Gromov-Hyperbolic Graphs
Bhaskar DasGupta, Marek Karpinski, Nasim Mobasheri, Farzaneh Yahyanejad
[Download PostScript] [Download PDF]

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.

Last Change: 10/30/15 at 11:06:51
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V