- INSTANCE:
A graph
,
a set
of terminals, and a weight
function
.
- SOLUTION:
A multiway cut, i.e., a set
such that the removal of
*E'*from*E*disconnects each terminal from all the others. - MEASURE:
The weight of the cut, i.e.,
.

*Good News:*Approximable within [95].*Bad News:*APX-complete [131].*Comment:*Admits a PTAS if every vertex has degree [39]. It remains APX-complete even if is fixed. For and it is approximable within 4/3 and 12/7, respectively. In the case of directed graphs the problem is approximable within 2 [383] and is APX-hard [188]. The vertex deletion variation is approximable within and is APX-complete [188].