A distributed algorithm for graph sparsification

Abstract

There has been plenty of work on graph cut sparsi cation. Previous works use either combinatorial graph techniques or algebraic graph techniques to obtain the most important parameter in a random sampling process, the probability pe for each edge e. Sampling each edge according to this pe respectively and giving each sampled edge e weight 1/pe yields a good cut sparsi cation of the original graph. This framework has been formalized and su cient conditions for the framework to work have also been developed in the past few years. However prior work has been restricted to centralized setting. Our main contribution is a distributed algorithm for graph sparsification. Our algorithm is designed on simple graphs and also later extended to multi-graphs and weighted graphs. On simple graphs we present an efficient algorithm for finding a skeleton with O(n log2 n2) edges in expectation with running time O(n log2 n). For weighted graphs with polynomial weights, our algorithm takes O(n 1+dlog2 n) time where d is some constant and edge weight is bounded by nd . Our algorithm takes O(nan log n) time for exponential weighted graphs where edge weight is bounded by a n. Our approach uses of random weight minimum spanning tree (RWMST), which is the minimum spanning tree (MST) computed when independently assigning random weight to each edge in the graph. We show an efficient way to approximate edge connectivity using this idea of RWMST and random sampling. Our algorithms are Monte-Carlo, i.e. work with high probability (whp).