Capacitated network design on undirected graphs

In this paper, we study the approximability of the capacitated network design problem (Cap-NDP) on undirected graphs: Given G = (V,E) with non-negative costs c and capacities u on its edges, source-sink pairs (s_i, t _i) with demand r_i, the goal is to find the minimum cost subgraph where the minimum (s_i, t_i) cut with u-capacities is at least r_i. When u ≡ 1, we get the usual SNDP for which Jain gave a 2-approximation algorithm [9]. Prior to our work, the approximability of undirected Cap-NDP was not well understood even in the single source-sink pair case. In this paper, we show that the single-source pair Cap-NDP is label-cover hard in undirected graphs. An important special case of single source-sink pair undirected Cap-NDP is the following source location problem. Given an undirected graph, a collection of sources S and a sink t, find the minimum cardinality subset S′ ⊆ S such that flow(S′, t), the maximum flow from S′ to t, equals flow(S, t). In general, the problem is known to be set-cover hard. We give a O(ρ)-approximation when flow(s, t) ≈_ρ flow(s′, t) for s, s′ ∈ S, that is, all sources have max-flow values to the sink within a multiplicative ρ factor of each other. The main technical ingredient of our algorithmic result is the following theorem which may have other applications. Given a capacitated, undirected graph G with a dedicated sink t, call a subset X ⊆ V irreducible if the maximum flow f(X) from X to t is strictly greater than that from any strict subset X′ ⊂ X, to t. We prove that for any irreducible set, X, the flow f(X) ≥ 1/2 ∑_i∈X f_i, where f _i is the max-flow from i to t. That is, undirected flows are quasi-additive on irreducible sets.