A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
MohammadAli Safari, Mohammad R. Salavatipour · SIAM Journal on Discrete Mathematics · 2011
In the [Formula: see text]-subgraph problem, we are given an undirected graph [Formula: see text] with edge costs and two positive integers [Formula: see text] and [Formula: see text], and the goal is to find a minimum cost simple [Formula: see text]-edge-connected subgraph of [Formula: see text] with at least [Formula: see text] nodes. This generalizes several classical problems, such as the minimum cost [Formula: see text]-spanning tree problem, or [Formula: see text]-MST (which is a [Formula: see text]-subgraph), and the minimum cost [Formula: see text]-edge-connected spanning subgraph (which is a [Formula: see text]-subgraph). The only previously known results on this problem [L. C. Lau, J. S. Naor, M. R. Salavatipour and M. Singh, SIAM J. Comput., 39 (2009), pp. 1062–1087], [C. Chekuri and N. Korula, in Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Bangalore, India, LIPIcs 2, Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2008, pp. 119–130] show that the [Formula: see text]-subgraph problem has an [Formula: see text]-approximation (even for 2-node-connectivity) and that the [Formula: see text]-subgraph problem in general is almost as hard as the densest [Formula: see text]-subgraph problem. In this paper we show that if the edge costs are metric (i.e., satisfy the triangle inequality), like in the [Formula: see text]-MST problem, then there is an [Formula: see text]-approximation algorithm for the [Formula: see text]-subgraph problem. This essentially generalizes the [Formula: see text]-MST constant factor approximability to higher connectivity.