TY - JOUR

T1 - Approximating node connectivity problems via set covers

AU - Kortsarz, Guy

AU - Nutov, Zeev

N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

PY - 2003/10

Y1 - 2003/10

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Metric costs

KW - k-Vertex connected spanning subgraph

UR - http://www.scopus.com/inward/record.url?scp=0942290222&partnerID=8YFLogxK

U2 - 10.1007/s00453-003-1027-4

DO - 10.1007/s00453-003-1027-4

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:0942290222

SN - 0178-4617

VL - 37

SP - 75

EP - 92

JO - Algorithmica

JF - Algorithmica

IS - 2

ER -