License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.15
URN: urn:nbn:de:0030-drops-63667
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6366/
Go to the corresponding LIPIcs Volume Portal

Bläsius, Thomas ; Friedrich, Tobias ; Krohmer, Anton

Hyperbolic Random Graphs: Separators and Treewidth

pdf-format:
LIPIcs-ESA-2016-15.pdf (0.6 MB)

Abstract

Hyperbolic random graphs share many common properties with complex real-world networks; e.g., small diameter and average distance, large clustering coefficient, and a power-law 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 worst-case run-time is then replaced by the expected run-time or by bounds that hold with high probability (whp), i.e., with probability 1-O(1/n). Though many structural properties of hyperbolic random graphs have been studied, almost no algorithmic results are known.

Divide-and-conquer 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/2-beta/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/2-beta/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:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6366},
  URN =		{urn:nbn:de:0030-drops-63667},
  doi =		{10.4230/LIPIcs.ESA.2016.15},
  annote =	{Keywords: hyperbolic random graphs, scale-free networks, power-law graphs, separators, treewidth}
}

Keywords: hyperbolic random graphs, scale-free networks, power-law graphs, separators, treewidth
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI