Next: MINIMUM BICONNECTIVITY AUGMENTATION Up: Cuts and Connectivity Previous: MINIMUM K-VERTEX CONNECTED SUBGRAPH Index

### MINIMUM K-EDGE CONNECTED SUBGRAPH

- INSTANCE: Graph . k is a constant, .

- SOLUTION: A k-edge connected spanning subgraph for G, i.e. a spanning subgraph that cannot be disconnected by removing fewer than k edges.

- MEASURE: The cardinality of the spanning subgraph, i.e., |E'|.

- Good News: Approximable within 1.704 [295], [101] and [149].
- Bad News: APX-complete even for k=2 [149].
- Comment: Approximable within for even k and within for odd k [101] and [149]. On directed graphs the problem is approximable within 1.61 for k=1 [300], within 2 for , and within 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 for every k [303].