Approximating node connectivity problems via set covers

Guy Kortsarz, Zeev Nutov

Research output: Contribution to journalArticle

61 Scopus citations

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 ku for every node u are given, and the aim is to find a minimum-cost subgraph that contains max{ku, kv} 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 ku. 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 languageEnglish (US)
Pages (from-to)75-92
Number of pages18
JournalAlgorithmica (New York)
Volume37
Issue number2
DOIs
StatePublished - Oct 1 2003

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Approximating node connectivity problems via set covers'. Together they form a unique fingerprint.

  • Cite this