License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2008.1746
URN: urn:nbn:de:0030-drops-17469
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1746/
Go to the corresponding LIPIcs Volume Portal

Chekuri, Chandra ; Korula, Nitish

Pruning 2-Connected Graphs

pdf-format:
08004.ChekuriChandra.1746.pdf (0.4 MB)

Abstract

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

BibTeX - Entry

@InProceedings{chekuri_et_al:LIPIcs:2008:1746,
  author =	{Chandra Chekuri and Nitish Korula},
  title =	{{Pruning 2-Connected Graphs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{119--130},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Ramesh Hariharan and Madhavan Mukund and V Vinay},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1746},
  URN =		{urn:nbn:de:0030-drops-17469},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1746},
  annote =	{Keywords: 2-Connected Graphs, k-MST, Density, Approximation}
}

Keywords: 2-Connected Graphs, k-MST, Density, Approximation
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue Date: 2008
Date of publication: 05.12.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI