Multi-way cut in undirected graphs

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

For $k = 2$, 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 $k \geq 3$. Dahlhaus et al. give a simple combinatorial isolation heuristic that that is $2 - \frac{2}{k}$-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 $1.5 - \frac{1}{k}$ 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 $k - 1$ 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] $2 - \frac{2}{k}$
Linear Prog. Relaxation [2] $1.5 - \frac{1}{k}$
Geometric Embedding Relaxation [3] $1.348$

Ali Salehi 2005-04-29