TY - GEN

T1 - Pruning 2-connected graphs

AU - Chekuri, Chandra

AU - Korula, Nitish

PY - 2008

Y1 - 2008

N2 - Given an edge-weighted undirected graph G with a specified set of terminals, let the density of any subgraph be the ratio of its weight/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 prune G and find such subgraphs of any desired size, at the cost of only a logarithmic increase in density (plus a small additive factor). We apply the 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 the 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 n log k) approximation for the k-2VC problem, and a bicriteria approximation for the Budget-2VC problem that gives an O(1/ε log2n) approximation, while violating the budget by a factor of at most 3 + ε.

AB - Given an edge-weighted undirected graph G with a specified set of terminals, let the density of any subgraph be the ratio of its weight/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 prune G and find such subgraphs of any desired size, at the cost of only a logarithmic increase in density (plus a small additive factor). We apply the 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 the 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 n log k) approximation for the k-2VC problem, and a bicriteria approximation for the Budget-2VC problem that gives an O(1/ε log2n) approximation, while violating the budget by a factor of at most 3 + ε.

KW - 2-Connected Graphs

KW - Approximation

KW - Density

KW - K-MST

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

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

M3 - Conference contribution

AN - SCOPUS:84880216080

SN - 9783939897088

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 119

EP - 130

BT - FSTTCS 2008 - IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

T2 - 28th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008

Y2 - 9 December 2008 through 11 December 2008

ER -