## Abstract

Given a graph (directed or undirected) with costs on the edges, and an integer k, we consider the problem of finding a k-node connected spanning subgraph of minimum cost. For the general instance of the problem (directed or undirected), there is a simple 2k-approximation algorithm. Better algorithms are known for various ranges of n, k. For undirected graphs with metric costs Khuller and Raghavachari gave a (2 + 2(k - 1)/n)-approximation algorithm. We obtain the following results: (i) For arbitrary costs, a k-approximation algorithm for undirected graphs and a (k + 1)-approximation algorithm for directed graphs. (ii) For metric costs, a (2 + (k - 1)/n)-approximation algorithm for undirected graphs and a (2 + k/n)-approximation algorithm for directed graphs. For undirected graphs and k = 6, 7, we further improve the approximation ratio from k to ⌈(k + 1)/2⌉ = 4; previously, ⌈(k + 1)/2⌉-approximation algorithms were known only for k ≤ 5. We also give a fast 3-approximation algorithm for k = 4. The multiroot problem generalizes the min-cost k-connected subgraph problem. In the multiroot problem, requirements k_{u} for every node u are given, and the aim is to find a minimum-cost subgraph that contains max{k_{u}, k_{v}} internally disjoint paths between every pair of nodes u, v. For the general instance of the problem, the best known algorithm has approximation ratio 2k, where k = max k_{u}. For metric costs there is a 3-approximation algorithm. We consider the case of metric costs, and, using our techniques, improve for k ≤ 7 the approximation guarantee from 3 to 2 + ⌊(k - 1)/2⌋/k < 2.5.

Original language | English (US) |
---|---|

Pages (from-to) | 75-92 |

Number of pages | 18 |

Journal | Algorithmica (New York) |

Volume | 37 |

Issue number | 2 |

DOIs | |

State | Published - Oct 2003 |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- Computer Science Applications
- Applied Mathematics

## Keywords

- Approximation algorithms
- Metric costs
- k-Vertex connected spanning subgraph