10.4230/LIPICS.FSTTCS.2008.1746
Chekuri, Chandra
Chandra
Chekuri
Korula, Nitish
Nitish
Korula
Pruning 2-Connected Graphs
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Article
2-Connected Graphs
k-MST
Density
Approximation
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
2008
2008-12-05
2008-12-05
2008-12-05
en
urn:nbn:de:0030-drops-17469
10.4230/LIPIcs.FSTTCS.2008
978-3-939897-08-8
1868-8969
10.4230/LIPIcs.FSTTCS.2008
LIPIcs, Volume 2, FSTTCS 2008
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
2
28
119
130
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
2
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
442177 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
Given an edge-weighted 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
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 \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 NP-Hard
problems on finding large 2-vertex-connected 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 minimum-cost
2-vertex-connected 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 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 \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$.
LIPIcs, Vol. 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 119-130