Treffer: An improved analysis for approximating the smallest κ-edge connected spanning subgraph of a multigraph

Khuller and Raghavachari [J. Algorithms, 21 (1996), pp. 434-450] present an approximation algorithm (the KR algorithm) for finding the smallest k-edge connected spanning subgraph (k-ECSS) of an undirected multigraph. They prove the KR algorithm has an approximation ratio < 1.85. We improve this bound to ≤ 1 + √1/e < 1.61 (for odd k we modify the base case of the KR algorithm). This is the best-known performance bound for a combinatorial approximation algorithm for the smallest k-ECSS problem for arbitrary k. Our analysis also gives the best-known combinatorial performance bound for any fixed value of k > 3, e.g., for even k the approximation ratio is < 1 + (1 - 1 k)k/2. Our analysis is based on a laminar family of sets (similar to families used in related contexts) which gives a better accounting of edges added in previous iterations of the algorithm. We also present a polynomial time implementation of the KR algorithm on multigraphs, running in the time for O(nm) maximum flow computations, where n (m) is the number of vertices (edges, not counting parallel copies), respectively. This complements the implementation of Khuller and Raghavachari [J. Algorithms, 21 (1996), pp. 434-450] which uses time O((kn)2) and is efficient for small k.