TY - JOUR

T1 - Pruning 2-connected graphs

AU - Chekuri, Chandra

AU - Korula, Nitish

N1 - Funding Information:
When this work was done, N. Korula was at the Department of Computer Science at the University of Illinios, and was partially supported by NSF grant CCF 0728782.
Funding Information:
C. Chekuri was partially supported by NSF grants CCF 0728782 and CNS-0721899, and a US-Israeli BSF grant 2002276.

PY - 2012/2

Y1 - 2012/2

N2 - Given an undirected graph G with edge costs and a specified set of terminals, let the density of any subgraph be the ratio of its cost to the number of terminals it contains. If G is 2-connected, does it contain smaller 2-connected subgraphs of density comparable to that of G? We answer this question in the affirmative by giving an algorithm to pruneG and find such subgraphs of any desired size, incurring only a logarithmic factor increase in density (plus a small additive term). We apply our pruning techniques to give algorithms for two NP-Hard problems on finding large 2-vertex-connected subgraphs of low cost; no previous approximation algorithm was known for either problem. In the k-2VC problem, we are given an undirected graph G with edge costs and an integer k; the goal is to find a minimum-cost 2-vertex-connected subgraph of G containing at least k vertices. In the Budget-2VC problem, we are given a graph G with edge costs, and a budget B; the goal is to find a 2-vertex-connected subgraph H of G with total edge cost at most B that maximizes the number of vertices in H. We describe an O(log∈nlog∈k) approximation for the k-2VC problem, and a bicriteria approximation for the Budget-2VC problem that gives an $O(\frac 1 \epsilon \log 2 n)$ approximation, while violating the budget by a factor of at most 2+ε.

AB - Given an undirected graph G with edge costs and a specified set of terminals, let the density of any subgraph be the ratio of its cost to the number of terminals it contains. If G is 2-connected, does it contain smaller 2-connected subgraphs of density comparable to that of G? We answer this question in the affirmative by giving an algorithm to pruneG and find such subgraphs of any desired size, incurring only a logarithmic factor increase in density (plus a small additive term). We apply our pruning techniques to give algorithms for two NP-Hard problems on finding large 2-vertex-connected subgraphs of low cost; no previous approximation algorithm was known for either problem. In the k-2VC problem, we are given an undirected graph G with edge costs and an integer k; the goal is to find a minimum-cost 2-vertex-connected subgraph of G containing at least k vertices. In the Budget-2VC problem, we are given a graph G with edge costs, and a budget B; the goal is to find a 2-vertex-connected subgraph H of G with total edge cost at most B that maximizes the number of vertices in H. We describe an O(log∈nlog∈k) approximation for the k-2VC problem, and a bicriteria approximation for the Budget-2VC problem that gives an $O(\frac 1 \epsilon \log 2 n)$ approximation, while violating the budget by a factor of at most 2+ε.

KW - 2-connected graphs

KW - Approximation

KW - Density

KW - Prize-collecting trees

KW - k-MST

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

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

U2 - 10.1007/s00453-010-9462-5

DO - 10.1007/s00453-010-9462-5

M3 - Article

AN - SCOPUS:84855340211

SN - 0178-4617

VL - 62

SP - 436

EP - 463

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 1-2

ER -