Approximating the minimum k-way cut in a graph via minimum 3-way cuts

For an edge weighted undirected graph G and an integer k > 2, a k-way cut i s a set of edges whose removal leaves G with at least k components. We prop ose a simple approximation algorithm to the minimum k-way cut problem. It c omputes a nearly optimal k-way cut by using a set of minimum 3-way cuts. We show that the performance ratio of our algorithm is 2 - 3/k for an odd k a nd 2 - (3k - 4)/(k(2) - k) for an even k. The running time is O(kmn(3) log( n(2)/m)) where n and m are the numbers of vertices and edges respectively.