Next: MINIMUM MULTI-CUT
Up: Cuts and Connectivity
Previous: MINIMUM VERTEX K-CUT
of terminals, and a weight
A multiway cut, i.e., a set
such that the removal of E'
from E disconnects each terminal from all the others.
The weight of the cut, i.e.,
- Good News:
- Bad News:
Admits a PTAS if every vertex has degree
It remains APX-complete even if
it is approximable within 4/3 and 12/7,
In the case of directed graphs the problem is approximable within 2 
and is APX-hard .
The vertex deletion variation is approximable within