The k-terminal cut problem, also known as the Multiway Cut problem, is defined on an edge-weighted graph with A; distinct vertices called "terminals." The goal is to remove a minimum weight collection of edges from the graph such that there is no path between any pair of terminals. The problem is NP-hard. Isolating cuts are minimum cuts which separate one terminal from the rest. The union of all the isolating cuts, except the largest, is a (2-2/k)-approximation to the optimal k-terrninal cut. This is the only currently-known approximation algorithm for k-terminal cut which does not require solving a linear program. An instance of k-terminal cut is γ-stable if edges in the cut can be multiplied by up to γ without changing the unique optimal solution. In this paper, we show that, in any (k-1)-stable instance of k-terminal cut, the source sets of the isolating cuts are the source sets of the unique optimal solution of that k-terminal cut instance. We conclude that the (2-2/k)-approximation algorithm returns the optimal solution on (k-1)-stable instances. Ours is the first result showing that this (2-2/k)-approximation is an exact optimization algorithm on a special class of graphs. We also show that our (k-1)-stability result is tight. We construct (k-1-ε)-stable instances of the k-terminal cut problem which only have trivial isolating cuts: that is, the source set of the isolating cut for each terminal is just the terminal itself. Thus, the (2-2/k)-approximation does not return an optimal solution.
展开▼
