Single-Sink Network Design with Vertex Connectivity Requirements

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