Graph explorer

Distributed Connectivity Decomposition

We present time-efficient distributed algorithms for decomposing graphs with large edge or vertex connectivity into multiple spanning or dominating trees, respectively. As their primary applications, these decompositions allow us to achieve information 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 vertex-connectivity $k$ into (fractionally) vertex-disjoint weighted dominating trees with total weight $Ω(\frac{k}{\log n})$, in $\widetilde{O}(D+\sqrt{n})$ rounds. (II) A decomposition of each undirected graph with edge-connectivity $λ$ into (fractionally) edge-disjoint weighted spanning trees with total weight $\lceil\frac{λ-1}{2}\rceil(1-\varepsilon)$, in $\widetilde{O}(D+\sqrt{nλ})$ rounds. We also show round complexity lower bounds of $\tildeΩ(D+\sqrt{\frac{n}{k}})$ and $\tildeΩ(D+\sqrt{\frac{n}λ})$ 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