- 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., .

*Good News:*Approximable within 1.704 [312], [109] and [161].*Bad News:*APX-complete even for*k=2*[161].*Comment:*Approximable within for even*k*and within for odd*k*[109] and [161]. On directed graphs the problem is approximable within 1.61 for*k=1*[317], within 2 for , and within for [109]. 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*[320]. Admits a PTAS for complete Euclidean graphs [130].