Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
share
In the minimum k-edge-connected spanning subgraph (k-ECSS) problem the goal is to find the minimum weight subgraph resistant to up to k-1 edge failures. This is a central problem in network design, and a natural generalization of the minimum spanning tree (MST) problem. While the MST problem has been studied extensively by the distributed computing community, for k ≥ 2 less is known in the distributed setting. In this paper, we present fast randomized distributed approximation algorithms for k-ECSS in the CONGEST model. Our first contribution is an O(D + √(n))-round O(n)-approximation for 2-ECSS, for a graph with n vertices and diameter D. The time complexity of our algorithm is almost tight and almost matches the time complexity of the MST problem. For larger constant values of k we give an O(n)-round O(n)-approximation. Additionally, in the special case of unweighted 3-ECSS we show how to improve the time complexity to O(D ^3n) rounds. All our results significantly improve the time complexity of previous algorithms.
READ FULL TEXT