A 4 + ϵ approximation for k-connected subgraphs

We obtain approximation ratio [Formula presented] for the (undirected) k-CONNECTED SUBGRAPH problem, where [Formula presented] is the largest integer such that 2^ℓ−1k^2ℓ+1≤n. For large values of n this improves the ratio 6 of Cheriyan and Végh [4] when n≥k³ (the case ℓ=1). Our result implies an fpt-approximation ratio 4+ϵ that matches (up to the “+ϵ” term) the best known ratio 4 for k=6,7 for both the general and the easier augmentation versions of the problem. Similar results are shown for the problem of covering an arbitrary symmetric crossing supermodular biset function.