2011/04/20 by Bundit Laekhanukit, Laekhanukit, Bundit
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1104.3923
arxiv created 2013/01/18 · arxiv updated 2013/01/21
The minimum-cost subset k-connected subgraph problem is a cornerstone problem in the area of network design with vertex connectivity requirements. In this problem, we are given a graph G=(V,E) with costs on edges and a set of terminals T. The goal is to find a minimum cost subgraph such that every pair of terminals are connected by k openly (vertex) disjoint paths. In this paper, we present an approximation algorithm for the subset k-connected subgraph problem which improves on the previous best approximation guarantee of O(k2logk) by Nutov (FOCS 2009). Our approximation guarantee, α(|T|), depends upon the number of terminals: [α(|T|) = O(|T|2) & if |T| < 2k O(k log2 k) & if 2k≤ |T| < k2 O(k log k) & if |T| ≥ k2] So, when the number of terminals is \em large enough, the approximation guarantee improves significantly. Moreover, we show that, given an approximation algorithm for |T|=k, we can obtain almost the same approximation guarantee for any instances with |T|> k. This suggests that the hardest instances of the problem are when |T|≈ k.