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