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.OPODIS.2015.10
URN: urn:nbn:de:0030-drops-66014
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6601/
Go to the corresponding LIPIcs Volume Portal

Kuhn, Fabian ; Molla, Anisur Rahaman

Distributed Sparse Cut Approximation

pdf-format:
LIPIcs-OPODIS-2015-10.pdf (1 MB)

Abstract

We study the problem of computing a sparse cut in an undirected network graph G=(V,E). We measure the sparsity of a cut (S,V\S) by its conductance phi(S), i.e., by the ratio of the number of edges crossing the cut and the sum of the degrees on the smaller of the two sides. We present an efficient distributed algorithm to compute a cut of low conductance. Specifically, given two parameters b and phi, if there exists a cut of balance at least b and conductance at most phi, our algorithm outputs a cut of balance at least b/2 and conductance at most ~O(sqrt{phi}), where ~O(.) hides polylogarithmic factors in the number of nodes n. Our distributed algorithm works in the \congest model, i.e., it only requires to send messages of size at most O(log(n)) bits. The time complexity of the algorithm is ~O(D + 1/b*phi), where D is the diameter of G. This is a significant improvement over a result by Das Sarma et al. [ICDCN 2015], where it is shown that a cut of the same quality can be computed in time ~O(n + 1/b*phi). The improved running time is in particular achieved by devising and applying an efficient distributed algorithm for the all-prefix-sums problem in a distributed search tree. This algorithm, which is based on the classic parallel all-prefix-sums algorithm, might be of independent interest.

BibTeX - Entry

@InProceedings{kuhn_et_al:LIPIcs:2016:6601,
  author =	{Fabian Kuhn and Anisur Rahaman Molla},
  title =	{{Distributed Sparse Cut Approximation}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{1--14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Emmanuelle Anceaume and Christian Cachin and Maria Potop-Butucaru},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6601},
  URN =		{urn:nbn:de:0030-drops-66014},
  doi =		{10.4230/LIPIcs.OPODIS.2015.10},
  annote =	{Keywords: sparsest cut, conductance, random walks, all-prefix-sums}
}

Keywords: sparsest cut, conductance, random walks, all-prefix-sums
Collection: 19th International Conference on Principles of Distributed Systems (OPODIS 2015)
Issue Date: 2016
Date of publication: 13.10.2016

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