The Steiner k-Cut Problem

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 ⊆ V called { terminals}, and an integer k ≤ |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-2/k)-approximation based on Gomory--Hu trees, and a (2 - 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$).