For , the problem is reduced to the s-t min-cut introduced by Ford and Fulkerson and known to have a polynomial time solution . For undirected graphs, Multi-way cut terminal problem is known to be NP-hard for . Dahlhaus et al. give a simple combinatorial isolation heuristic that that is -approximate. In this algorithm for each terminal, a minimum cut that separates that terminal from the other terminals is calculated and union of these cuts give the approximation of the multi-cut .
Calinescu et al. give an improved approximation algorithm, achieving performance ratio, based on linear programming relaxation for the multi-way cut problem. Their algorithm consists of three setps. First, an optimal solution for multi-way cut relaxation is found. Then they perform a relaxation by placing the terminals at the vertices of a simplex (a feasible solution of a linear program) and other nodes anywhere in the simplex. Finally, a rounding algorithm is applied where all nodes are placed at the vertices with permutation .
Karger et al. prove the existence of a 1.3488-approximate algorithm for undirected graphs by formulating the problem of k way cut as an infinite-dimensional linear programming problem .
|Alg. for Undirected Graphs||App. Ratio|
|Isolation Heuristic |
|Linear Prog. Relaxation |
|Geometric Embedding Relaxation |
Ali Salehi 2005-04-29