, a set
of source-terminal
pairs, and a weight function
.
such that the removal of
E'
from
E
disconnects
from
for every pair
.
.
[
128
]
[
127
].
The variation in which the input specifies a set of demand edges and a
given node
and the solution must be a feasible
-cut,
i.e., the demand edges must either be in the cut or have both
endpoints on the opposite part of
is approximable within
2.8 [
348
].
Viggo Kann