On Some Network Design Problems With Degree Constraints
In network design problems one seeks a cheap subgraph H of a given graph G that satisfies some given properties. In the b-Matching problem H should satisfy prescribed degree constraints, while in the Survivable Network problem H should satisfy prescribed connectivity requirements. The Degree-Constrained Survivable Network problems is a combination of these two fundamental problems, where H should satisfy both degree constraints and connectivity requirements. For most of these problems, even checking whether there exists a feasible solution is NP-hard, hence one considers a bicriteria approximation when the degree constraints are relaxed. Namely, the goal is to compute a cheap solution that satisfies the connectivity requirements and has small degree violation.