Next: MINIMUM MULTI-CUT
Up: Cuts and Connectivity
Previous: MINIMUM VERTEX K-CUT
  Index
- 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].
Viggo Kann
1999-04-22