A 4 + ε approximation for k-connected subgraphs

We obtain approximation ratio 2(2 + 1 ℓ ) for the (undirected) k-Connected Subgraph problem, where ℓ ≈ 1 2 (log k n-1) is the largest integer such that 2 ℓ-1 k 2ℓ+1 ≤ n. For large values of n this improves the 6-approximation of Cheriyan and Végh [4] when n = Ω(k 3 ), which is the case ℓ = 1. For k bounded by a constant we obtain ratio 4 + ǫ.

For large values of n our ratio matches the best known ratio 4 for the augmentation version of the problem [28,29], as well as the best known ratios for k = 6, 7 [22]. Similar results are shown for the problem of covering an arbitrary crossing supermodular biset function. General Augmentation Undirected Directed Undirected Directed O ln n n-k • ln k [28] O ln n n-k • ln k [28] 2H(µ) + 1 [29] H(µ) + 3/2 [29] 6 if n ≥ k 3 [4] (see also [16]) O(ln(n -k)) [28] O(ln(n -k)) [28] ⌈(k + 1)/2⌉ if k ≤ 7 [2,6,22] k + 1 if k ≤ 6 [22]