For , the problem is reduced to the s-t min-cut introduced by Ford and Fulkerson and known to have a polynomial time solution [2]. 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 [1].

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 [2].

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 [3].

Alg. for Undirected Graphs | App. Ratio |

Isolation Heuristic [1] | |

Linear Prog. Relaxation [2] | |

Geometric Embedding Relaxation [3] |

Ali Salehi 2005-04-29