THE COMPLEXITY OF MULTITERMINAL CUTS

In the multiterminal cut problem one is given an edge-weighted graph a nd a subset of the vertices called terminals, and is asked for a minim um weight set of edges that separates each terminal from all the other s. When the number k of terminals is two, this is simply the mincut, m ax-flow problem, and can be solved in polynomial time. It is shown tha t the problem becomes NP-hard as soon as k = 3, but can be solved in p olynomial time for planar graphs for any fixed k. The planar problem i s NP-hard, however, if k is not fixed. A simple approximation algorith m for arbitrary graphs that is g guaranteed to come within a factor of 2 - 2/k of the optimal cut weight is also described.