Next: MINIMUM MULTI-CUT Up: Cuts and Connectivity Previous: MINIMUM VERTEX K-CUT Index

### MINIMUM MULTIWAY CUT

- 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 3/2-1/|S| [87].

- Bad News: APX-complete [122].

- Comment: Admits a PTAS if every vertex has degree [37]. It remains APX-complete even if is fixed. For |S|=4 and |S|=8 it is approximable within 4/3 and 12/7, respectively. In the case of directed graphs the problem is approximable within 2 [362] and is APX-hard [176]. The vertex deletion variation is approximable within 2-2/|S| and is APX-complete [176].