Next: MINIMUM RATIO-CUT Up: Cuts and Connectivity Previous: MINIMUM MULTIWAY CUT Index

### MINIMUM MULTI-CUT

- 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 si from ti for every pair .

- MEASURE: The weight of the cut, i.e., .

- Good News: Approximable within [177]

- 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 [178]. The variation in which vertices instead of edges should be deleted is also approximable within [176]. The variation in which the input specifies a set of demand edges and a given node v* and the solution must be a feasible v*-cut, i.e., the demand edges must either be in the cut or have both endpoints on the opposite part of v* is approximable within 2.8 [449].