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 $\gamma$-stable graphs, a notion introduced by Bilu and Linial. An instance of k-terminal cut is said to be $\gamma$-stable if edges in the cut can be multiplied by up to $\gamma$ without changing the optimal solution. The best-known result to date for $\gamma$-stable instances of k-terminal cut states that the problem can be solved in polynomial time for $\gamma \geq 4$ by solving a certain linear program. In this paper, we improve this and show that $\gamma$-stable instances of k-terminal cut can be solved in polynomial time for $\gamma \geq 2$. The result is surprising: we show that a known 2-approximation algorithm for the problem actually delivers the unique optimal solution for 2-stable graphs. The algorithm utilizes only minimum cut procedures, obviating the use of linear programming.
from cs updates on arXiv.org https://ift.tt/2K1Y9d2
//
0 comments:
Post a Comment