- INSTANCE:
A graph
,
a set
of source-terminal
pairs, and a weight function
.
- SOLUTION:
A multi-cut, i.e., a set
such that the removal of
*E'*from*E*disconnects from for every pair . - MEASURE:
The weight of the cut, i.e.,
.

*Good News:*Approximable within [189]*Bad News:*APX-hard.*Comment:*Generalization of MINIMUM MULTIWAY CUT. When the graph is a tree the problem is approximable within 2 and is APX-complete even for trees of height one and unit edge weight [190]. The variation in which vertices instead of edges should be deleted is also approximable within [188]. The variation in which the input specifies a set of demand edges and a given node and the solution must be a feasible -cut, i.e., the demand edges must either be in the cut or have both endpoints on the opposite part of is approximable within 2.8 [473].