.
k
is a constant,
.
for
G
,
i.e. a spanning subgraph that cannot be disconnected by removing fewer
than
k
edges.
for even
k
and within
for odd
k
[
72
] and [
107
].
On directed graphs the problem is approximable within 1.61 for
k=1
[
226
], within 2 for
,
and within
for
[
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 for every
k
[
229
].
Viggo Kann