A Polynomial-Time Algorithm for (2-2/k)-stable Instances of the k-terminal cut Problem
share
The k-terminal cut problem is defined on an edge-weighted graph with k 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 k-terminal cut problem is known to be NP-hard. There has been interest in determining special classes of graphs for which k-terminal cut can be solved in polynomial time. One special class of graphs is the class of γ-stable graphs, a notion introduced by Bilu and Linial. An instance of k-terminal cut is said to be γ-stable if edges in the cut can be multiplied by up to γ without changing the optimal solution. For several years, the best-known result for γ-stable instances of k-terminal cut stated that the problem can be solved in polynomial time for γ≥ 4 by solving a certain linear program. This result was recently improved to γ≥ 2 - 2/k using the same linear program. In this paper, we match the result, showing that γ-stable instances of k-terminal cut can be solved in polynomial time for γ≥ 2 - 2/k, with a faster algorithm. The result is surprising: we show that a known (2 - 2/k)-approximation algorithm for the problem actually delivers the unique optimal solution for (2 - 2/k)-stable graphs. The algorithm utilizes only minimum cut procedures, obviating the use of linear programming.
READ FULL TEXT