A 4 + ε approximation for k-connected subgraphs
Zeev Nutov · Society for Industrial and Applied Mathematics eBooks · 2019
We obtain approximation ratio for the (undirected) k-Connected Subgraph problem, where is the largest integer such that 2ℓ–1k2ℓ+1 ≤ n. For large values of n this improves the ratio 6 of Cheriyan and Végh [4] when n ≥ k3 (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 crossing supermodular biset function.