## Multi-way cut in undirected graphs

Given a graph and a set of terminal vertices, a Multi-way cut (also known as k way-cut) is a set of edges such that in , no path exists between any two nodes of . The Multi-way cut problem is defined as finding the multi-way cut where is minimal.

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