A 4 + ϵ approximation for k-connected subgraphs

摘要

We obtain approximation ratio 4+2ℓ≈4+4lg⁡klg⁡n−lg⁡k for the (undirected) k-Connected Subgraph problem, where ℓ=⌊lg⁡n−lg⁡k+12lg⁡k+1⌋ 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 symmetric crossing supermodular biset function.