Single-Sink Network Design with Vertex Connectivity Requirements

Chandra Chekuri & Nitish Korula
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...