.
k
is a constant,
.
for
G
,
i.e. a spanning subgraph that cannot be disconnected by removing fewer
than
k
vertices.
[
72
].
Variation in which each edge has a nonnegative weight and the
objective is to minimize the total weight of the spanning subgraph is
approximable within
2+1/|V|
for
k=2
[
221
]
and within 2
for
k>2
[
310
].
If the weight function satisfies the triangle inequality, the problem is
approximable within 3/2 for
k=2
[
114
] and within
2+2(k-1)/|V|
for
k>2
[
221
].
Viggo Kann