Distributed Connectivity Decomposition

A fundamental problem in distributed network algorithms is to manage congestion and obtain information flow matching the graph's connectivity. In this paper, we present time-efficient distributed algorithms for decomposing graphs with large edge or vertex connectivity into multiple spanning or dominating trees, respectively. These decompositions allow us to achieve a flow with size close to the connectivity by parallelizing it along the trees. More specifically, our distributed decomposition algorithms are as follows: (I) A decomposition of each undirected graph with vertexconnectivity k into (fractionally) vertex-disjoint weighted dominating trees with total weight Omega(k/log n), in (O)over tilde(D + root n) rounds in networks, where each node can send a total of at most O(log n) bits per round. (II) A decomposition of each undirected graph with edgeconnectivity. into (fractionally) edge-disjoint weighted spanning trees with total weight inverted right perpendicular lambda-1/2right perpendicular in (O)over tilde(D+root n lambda) rounds, if in each round, each edge can carry at most O(log n) bits of information. We also show round complexity lower bounds of (Omega)over tilde(D+root n/k) and (Omega)over tilde(D+root n/lambda) for the above two decompositions, using techniques of [Das Sarma et al., STOC'11]. Moreover, our vertex-connectivity decomposition extends to centralized algorithms and improves the time complexity of [Censor-Hillel et al., SODA'14] from O(n(3)) to near-optimal (O)over tilde(m). Additional implications of our results are: a near-linear time centralized approximation of vertex connectivity (which can be seen as a step towards a conjecture of Aho, Hopcroft and Ullman), the first distributed approximating of vertex connectivity, and distributed algorithms with near-optimal competitiveness for oblivious broadcast routing.