A simple randomized scheme for constructing low-weight k-connected spanning subgraphs with applications to distributed algorithms

AbstractThe main focus of this paper is the analysis of a simple randomized scheme for constructing low-weight k-connected spanning subgraphs. In this paper, we focus on the metric graph. We use the term metric graph for a complete graph with metric weights. We first show that our scheme gives a simple approximation algorithm to construct a minimum-weight k-connected spanning subgraph in a metric graph, an NP-hard problem. We show that our algorithm gives an approximation ratio of O(klogn) for a metric graph, O(k) for a random graph with nodes uniformly randomly distributed in [0,1]2 and O(lognk) for a complete graph with random edge weights U(0,1). We show that our scheme is optimal with respect to the amount of “local information” needed to compute any connected spanning subgraph. We then show that our scheme can be applied to design an efficient distributed algorithm for constructing such an approximate k-connected spanning subgraph (for any k≥1) in a point-to-point distributed model, where the processors form a complete network. Our algorithm takes O(lognk) time and an expected number of O(nklognk) messages. Our result in conjunction with a result of Korach et al. [E. Korach, S. Moran, S. Zaks, The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors, SIAM Journal on Computing 16 (2) (1987) 231–236] implies that the expected message complexity of our algorithm is significantly better than the best distributed algorithm that finds an optimal k-connected subgraph. We also show that for geometric instances, our randomized scheme constructs low-degree k-connected spanning subgraphs which have O(klogn) maximum degree, with high probability