The Steiner k-Cut Problem
Chandra Chekuri, Sudipto Guha, Joseph Seffi Naor · SIAM Journal on Discrete Mathematics · 2006
We consider the Steiner k-cut problem which generalizes both the k-cut problem and the multiway cut problem. The Steiner k-cut problem is defined as follows. Given an edge-weighted undirected graph $G=(V, E)$, a subset of vertices $X \subseteq V$ called {\em terminals}, and an integer $k \le |X|$, the objective is to find a minimum weight set of edges whose removal results in k disconnected components, each of which contains at least one terminal. We give two approximation algorithms for the problem: a greedy $(2-\frac{2}{k})$-approximation based on Gomory--Hu trees, and a $(2 - \frac{2}{|X|})$-approximation based on rounding a linear program. We use the insight from the rounding to develop an exact bidirected formulation for the global minimum cut problem (the k-cut problem with $k=2$).