DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2008.1746

Pruning 2-Connected Graphs

Authors: Chandra Chekuri and Nitish Korula

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

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

Cite as

Chandra Chekuri and Nitish Korula. Pruning 2-Connected Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 119-130, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:LIPIcs.FSTTCS.2008.1746,
  author =	{Chekuri, Chandra and Korula, Nitish},
  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 =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.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}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2008.1747

Single-Sink Network Design with Vertex Connectivity Requirements

Authors: Chandra Chekuri and Nitish Korula

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

Abstract

We study single-sink network design problems in undirected graphs with vertex connectivity requirements. The input to these problems is an edge-weighted undirected graph $G=(V,E)$, a sink/root vertex $r$, a set of terminals $T \subseteq V$, and integer $k$. The goal is to connect each terminal $t \in T$ to $r$ via $k$ \emph{vertex-disjoint} paths. In the {\em connectivity} problem, the objective is to find a min-cost subgraph of $G$ that contains the desired paths. There is a $2$-approximation for this problem when $k \le 2$ \cite{FleischerJW} but for $k \ge 3$, the first non-trivial approximation was obtained in the recent work of Chakraborty, Chuzhoy and Khanna \cite{ChakCK08}; they describe and analyze an algorithm with an approximation ratio of $O(k^{O(k^2)}\log^4 n)$ where $n=|V|$. In this paper, inspired by the results and ideas in \cite{ChakCK08}, we show an $O(k^{O(k)}\log |T|)$-approximation bound for a simple greedy algorithm. Our analysis is based on the dual of a natural linear program and is of independent technical interest. We use the insights from this analysis to obtain an $O(k^{O(k)}\log |T|)$-approximation for the more general single-sink {\em rent-or-buy} network design problem with vertex connectivity requirements. We further extend the ideas to obtain a poly-logarithmic approximation for the single-sink {\em buy-at-bulk} problem when $k=2$ and the number of cable-types is a fixed constant; we believe that this should extend to any fixed $k$. We also show that for the non-uniform buy-at-bulk problem, for each fixed $k$, a small variant of a simple algorithm suggested by Charikar and Kargiazova \cite{CharikarK05} for the case of $k=1$ gives an $2^{O(\sqrt{\log |T|})}$ approximation for larger $k$. These results show that for each of these problems, simple and natural algorithms that have been developed for $k=1$ have good performance for small $k > 1$.

Cite as

Chandra Chekuri and Nitish Korula. Single-Sink Network Design with Vertex Connectivity Requirements. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 131-142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:LIPIcs.FSTTCS.2008.1747,
  author =	{Chekuri, Chandra and Korula, Nitish},
  title =	{{Single-Sink Network Design with Vertex Connectivity Requirements}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{131--142},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1747},
  URN =		{urn:nbn:de:0030-drops-17475},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1747},
  annote =	{Keywords: Network Design, Vertex Connectivity, Buy-at-Bulk, Rent-or-Buy, Approximation}
}

Search Results

Documents authored by Korula, Nitish

Pruning 2-Connected Graphs

Abstract

Cite as

Single-Sink Network Design with Vertex Connectivity Requirements

Abstract

Cite as

Thanks for your feedback!

Could not send message