Bläsius, Thomas ;
Friedrich, Tobias ;
Krohmer, Anton
Hyperbolic Random Graphs: Separators and Treewidth
Abstract
Hyperbolic random graphs share many common properties with complex realworld networks; e.g., small diameter and average distance, large clustering coefficient, and a powerlaw degree sequence with adjustable exponent beta. Thus, when analyzing algorithms for large networks, potentially more realistic results can be achieved by assuming the input to be a hyperbolic random graph of size n. The worstcase runtime is then replaced by the expected runtime or by bounds that hold with high probability (whp), i.e., with probability 1O(1/n). Though many structural properties of hyperbolic random graphs have been studied, almost no algorithmic results are known.
Divideandconquer is an important algorithmic design principle that works particularly well if the instance admits small separators. We show that hyperbolic random graphs in fact have comparatively small separators. More precisely, we show that they can be expected to have balanced separator hierarchies with separators of size O(n^{3/2beta/2}), O(log n), and O(1) if 2 < beta < 3, beta = 3, and 3 < beta, respectively. We infer that these graphs have whp a treewidth of O(n^{3/2beta/2}), O(log^2 n), and O(log n), respectively. For 2 < \beta < 3, this matches a known lower bound.
To demonstrate the usefulness of our results, we give several algorithmic applications.
BibTeX  Entry
@InProceedings{blsius_et_al:LIPIcs:2016:6366,
author = {Thomas Bl{\"a}sius and Tobias Friedrich and Anton Krohmer},
title = {{Hyperbolic Random Graphs: Separators and Treewidth}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {15:115:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6366},
URN = {urn:nbn:de:0030drops63667},
doi = {10.4230/LIPIcs.ESA.2016.15},
annote = {Keywords: hyperbolic random graphs, scalefree networks, powerlaw graphs, separators, treewidth}
}
2016
Keywords: 

hyperbolic random graphs, scalefree networks, powerlaw graphs, separators, treewidth 
Seminar: 

24th Annual European Symposium on Algorithms (ESA 2016)

Issue date: 

2016 
Date of publication: 

2016 