Next: MINIMUM K-EDGE CONNECTED SUBGRAPH
Up: Cuts and Connectivity
Previous: MINIMUM QUOTIENT CUT
  Index
- INSTANCE:
Graph
.
k is a constant,
.
- SOLUTION:
A k-vertex connected spanning subgraph
for G,
i.e. a spanning subgraph that cannot be disconnected by removing fewer
than k vertices.
- MEASURE:
The cardinality of the spanning subgraph, i.e., |E'|.
- Good News:
Approximable within 1+1/k [174] and [101].
- Comment:
On directed graphs the problem is approximable within 1.61 for k=1
[300],
and within 1+1/k for
[101].
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 [295]
and within 2
for k>2 [398].
If the weight function satisfies the triangle inequality, the problem is
approximable within 3/2 for k=2 [161] and within
2+2(k-1)/|V| for k>2 [295].
- Garey and Johnson: GT31
Viggo Kann
1999-04-22