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 allprefixsums problem in a distributed search tree. This algorithm, which is based on the classic parallel allprefixsums 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 = {114},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897989},
ISSN = {18688969},
year = {2016},
volume = {46},
editor = {Emmanuelle Anceaume and Christian Cachin and Maria PotopButucaru},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6601},
URN = {urn:nbn:de:0030drops66014},
doi = {10.4230/LIPIcs.OPODIS.2015.10},
annote = {Keywords: sparsest cut, conductance, random walks, allprefixsums}
}
Keywords: 

sparsest cut, conductance, random walks, allprefixsums 
Collection: 

19th International Conference on Principles of Distributed Systems (OPODIS 2015) 
Issue Date: 

2016 
Date of publication: 

13.10.2016 