When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

TLDR

The generalized Steiner problem on networks requires selecting a minimum‑cost subgraph that satisfies edge‑connectivity requirements r_{ij} for every node pair. The authors aim to compute a minimum‑cost network meeting all requirements and present the first approximation algorithm for this problem. They develop an approximation algorithm based on a combinatorial min‑max equality between minimum‑cost networks and maximum cut packings, and extend it to an algorithm for optimally packing cuts to estimate probabilistic network reliability. The algorithm achieves a cost within 2 ⌈log₂(r + 1)⌉ of optimal, where r is the largest requirement, and the cut‑packing variant provides reliable network reliability estimates.

Abstract

We give the first approximation algorithm for the generalized network Steiner problem, a problem in network design. An instance consists of a network with link-costs and, for each pair $\{i, j\}$ of nodes, an edgeconnectivity requirement $r_{ij}$. The goal is to find a minimum-cost network using the available links and satisfying the requirements. Our algorithm outputs a solution whose cost is within $2 \lceil {\log_{2}(r + 1)} \rceil $ of optimal, where r is the highest requirement value. In the course of proving the performance guarantee, we prove a combinatorial minmax approximate equality relating minimum-cost networks to maximum packings of certain kinds of cuts. As a consequence of the proof of this theorem, we obtain an approximation algorithm for optimally packing these cuts; we show that this algorithm has application to estimating the reliability of a probabilistic network.