MINIMUM K-VERTEX CONNECTED SUBGRAPH

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

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

  
  

• Good News: Approximable within 1+1/k [186] and [109].

• Comment: On directed graphs the problem is approximable within 1.61 for k=1 [317], and within 1+1/k for $k\ge 2$ [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+1/\vert V\vert$ for k=2 [312] and within 2 $\sum_{i=1}^{k} \frac{1}{i}$ for k>2 [420]. If the weight function satisfies the triangle inequality, the problem is approximable within 3/2 for k=2 [173] and within $2+2(k-1)/\vert V\vert$ for k>2 [312].

• Garey and Johnson: GT31