Survivable Network Design with Degree or Order Constraints

We present algorithmic and hardness results for network design problems with degree or order constraints. We first consider the SURVIVABLE NETWORK DESIGN problem with degree constraints on vertices: the objective is to find a minimum cost subgraph satisfying certain connectivity requirements as well as degree upper bounds on the vertices. A well known special case is the MINIMUM BOUNDED DEGREE SPANNING TREE problem which has attracted much attention recently. Denote by Bv the degree constraint of vertex v. We present a (2, 2Bv + 3)-approximation algorithm for the element-connectivity SURVIVABLE NETWORK DESIGN problem with degree constraints on terminals, i.e., the cost of the solution is at most twice the optimum solution (satisfying the degree bounds), and the degree of each terminal vertex v is at most 2Bv + 3. This extends the most general network design model which admits a 2-approximation algorithm (with no degree constraints), and implies the first constant factor (bicriteria) approximation algorithms for many network design problems with degree constraints, including the MINIMUM BOUNDED DEGREE STEINER TREE problem. In the edge connectivity SURVIVABLE NETWORK DESIGN problem, the algorithm has an interesting feature that the average degree of the returned solution is only violated by an additive constant of 2. Our results also extend to directed graphs and we provide the first constant factor (bicriteria) approximation algorithms for, e.g., the MINIMUM BOUNDED DEGREE ARBORESCENCE problem and the MINIMUM BOUNDED DEGREE STRONGLY k-EDGE-CONNECTED SUBGRAPH problem. A striking aspect of our method is its simplicity. It is based on a natural extension of Jain’s iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems with degree constraints. In contrast, we show that the vertex-connectivity SURVIVABLE NETWORK DESIGN problem with degree constraints is very hard to approximate, even if the costs of all edges are zero. We also study the problem of finding a minimum cost λ-edgeconnected subgraph with at least k vertices, which we call the (k, λ)-subgraph problem. This generalizes some well-studied classical problems such as the k-MST and the minimum cost λ-edgeconnected subgraph problems. We give a poly-logarithmic approximation for the (k, 2)-subgraph problem. However, by relating it to the DENSEST k-SUBGRAPH problem, we give evidence that the (k, λ)-subgraph problem might be hard to approximate for arbitrary λ.