Degree-constrained node-connectivity

We give a general framework to handle node-connectivity degree constrained problems. In particular, for the κ-Outconnected Subgraph problem, for both directed and undirected graphs, our algorithm computes in polynomial time a solution J of cost O(log κ) times the optimal, such that deg _J (v) = O(2 ^κ ) • b(v) for all ν ∈ V. Similar result are obtained for the Element-Connectivity and the κ-Connected Subgraph problems. The latter is a significant improvement on the particular case of only degree-approximation and undirected graphs considered in [5]. In addition, for the edge-connectivity directed Degree-Constrained κ-Outconnected Subgraph problem, we slightly improve the best known approximation ratio, by a simple proof.