Erratum: Approximating minimum-cost connectivity problems via uncrossable bifamilies (ACM Transactions on Algorithms (2012) 9:1 (1) DOI: 10.1145/2390176.2390177)

There are two errors in our article “Approximating Minimum-Cost Connectivity Problems via Uncrossable Bifamilies” (ACM Transactions on Algorithms (TALG), 9(1), Article No. 1, 2012). In that article, we consider the (undirected) Survivable Network problem. The input consists of a graph G = (V, E) with edge-costs, a set T ⊆ V of terminals, and connectivity demands {r_st > 0: st ∈ D ⊆ T × T}. The goal is to find a minimum cost subgraph of G that for all st ∈ D contains r_st pairwise internally disjoint st-paths. We claimed ratios O(k ln k) for rooted demands when the set D of demand pairs form a star, where k = max_st ∈D r_st is the maximum demand. This ratio is correct when the requirements are r_st = k for all t ∈ T \ {s}, but for general rooted demands our article implies only ratio O(k²) (which, however, is still the currently best-known ratio for the problem). We also obtained various ratios for the node-weighted version of the problem. These results are valid, but the proof needs a correction described here.