, a set
of terminals, and a weight
function
.
such that the removal of
E'
from
E
disconnects each terminal from all the others.
.
[
89
].
[
24
].
It remains A
PX
-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
and A
PX
-hard [
127
].
The vertex deletion variation is approximable within 2-2/|
S
| and is
A
PX
-complete [
127
].
Viggo Kann