MINIMUM K-EDGE CONNECTED SUBGRAPH

• INSTANCE: Graph $G=\left(V,E\right)$. k is a constant, $k\ge 2$.

• SOLUTION: A k-edge connected spanning subgraph $G'=\left(V,E'\right)$ 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., $\vert E'\vert$.

  
  

• Good News: Approximable within 1.704 [312], [109] and [161].
• Bad News: APX-complete even for k=2 [161].
• Comment: Approximable within $\min\{1+5/k,7/4-(3k^2-6k+8)/(2k^2(3k-2))\}$ for even k and within $\min\{1+7/k,7/4-(2k-3)/(4k^2)\}$ for odd k [109] and [161]. On directed graphs the problem is approximable within 1.61 for k=1 [317], within 2 for $2\le k\le 16$, and within $1+4/\sqrt{k}$ for $k\ge 17$ [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].