Next: MINIMUM K-EDGE CONNECTED SUBGRAPH Up: Cuts and Connectivity Previous: MINIMUM QUOTIENT CUT Index

### MINIMUM K-VERTEX CONNECTED SUBGRAPH

- 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