Chekuri, Chandra ;
Korula, Nitish
Pruning 2Connected Graphs
Abstract
Given an edgeweighted undirected graph $G$ with a specified set of
terminals, let the \emph{density} of any subgraph be the ratio of
its weight/cost to the number of terminals it contains. If $G$ is
2connected, does it contain smaller 2connected subgraphs of
density comparable to that of $G$? We answer this question in the
affirmative by giving an algorithm to \emph{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 NPHard
problems on finding large 2vertexconnected subgraphs of low cost;
no previous approximation algorithm was known for either problem. In
the \kv problem, we are given an undirected graph $G$ with edge
costs and an integer $k$; the goal is to find a minimumcost
2vertexconnected subgraph of $G$ containing at least $k$
vertices. In the \bv\ problem, we are given the graph $G$ with edge
costs, and a budget $B$; the goal is to find a 2vertexconnected
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 \kv problem, and a bicriteria approximation
for the \bv\ problem that gives an $O(\frac{1}{\eps}\log^2 n)$
approximation, while violating the budget by a factor of at most
$3+\eps$.
BibTeX  Entry
@InProceedings{chekuri_et_al:LIPIcs:2008:1746,
author = {Chandra Chekuri and Nitish Korula},
title = {{Pruning 2Connected Graphs}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {119130},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897088},
ISSN = {18688969},
year = {2008},
volume = {2},
editor = {Ramesh Hariharan and Madhavan Mukund and V Vinay},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1746},
URN = {urn:nbn:de:0030drops17469},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2008.1746},
annote = {Keywords: 2Connected Graphs, kMST, Density, Approximation}
}
2008
Keywords: 

2Connected Graphs, kMST, Density, Approximation 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Issue date: 

2008 
Date of publication: 

2008 