We present new edge splitting-off results maintaining all-pairs edge-connectivities of an undirected graph. We first give an alternate proof of Mader's theorem, and use it to obtain a deterministic $\tilde{O}(m + {r_{\max}}^2 \cdot n^2)$-time complete edge splitting-off algorithm for unweighted graphs, where $r_{\max}$ denotes the maximum edge-connectivity requirement. This improves upon the best known algorithm by Gabow by a factor of $\tilde{\Omega}(n)$. We then prove a new structural property, and use it to further speed up the algorithm to obtain a randomized $\tilde{O}(m + {r_{\max}}^3 \cdot n)$-time algorithm. These edge splitting-off algorithms can be used directly to speed up various graph algorithms.

Given a complete undirected graph, a cost function on edges, and a degree bound B, the degree bounded network design problem is to find a minimum cost simple subgraph with maximum degree B satisfying given connectivity requirements. Even for a simple connectivity requirement such as finding a spanning tree, computing a feasible solution for the degree bounded network design problem is already NP-hard, and thus there is no polynomial factor approximation algorithm for this problem. In this paper, we show that when the cost function satisfies the triangle inequality, there are constant factor approximation algorithms for various degree bounded network design problems. In global edge-connectivity, there is a $(2+\frac{1}{k})$-approximation algorithm for the minimum bounded degree k-edge-connected subgraph problem. In local edge-connectivity, there is a 4-approximation algorithm for the minimum bounded degree Steiner network problem when $r_{\max}$ is even, and a 5.5-approximation algorithm when $r_{\max}$ is odd, where $r_{\max}$ is the maximum connectivity requirement. In global vertex-connectivity, there is a $(2+\frac{k-1}{n}+\frac{1}{k})$-approximation algorithm for the minimum bounded degree k-vertex-connected subgraph problem when $n\geq2k$, where n is the number of vertices. For spanning tree, there is a $(1+\frac{1}{B-1})$-approximation algorithm for the minimum bounded degree spanning tree problem. These approximation algorithms return solutions with the smallest possible maximum degree, and in most cases the cost guarantee is obtained by comparing to the optimal cost when there are no degree constraints. This demonstrates that degree constraints can be incorporated into network design problems with metric costs. Our algorithms can be seen as a generalization of Christofides' algorithm for the metric traveling salesman problem. The main technical tool is a simplicity-preserving edge splitting-off operation, which is used to “short-cut” vertices with high degree while maintaining connectivity requirements and preserving simplicity of the solutions.

Given a complete undirected graph, a cost function on edges and a degree bound B, the degree bounded network design problem is to find a minimum cost simple subgraph with maximum degree B satisfying given connectivity requirements. Even for simple connectivity requirement such as finding a spanning tree, computing a feasible solution for the degree bounded network design problem is already NP-hard, and thus there is no polynomial factor approximation algorithm for this problem. In this paper, we show that when the cost function satisfies triangle inequalities, there are constant factor approximation algorithms for various degree bounded network design problems.Global edge-connectivity: There is a (2+1/k)-approximation algorithm for the minimum bounded degree k-edge-connected subgraph problem. Local edge-connectivity: There is a 6-approximation algorithm for the minimum bounded degree Steiner network problem. Global vertex-connectivity: there is a (2+(k-1)/n+1/k)-approximation algorithm for the minimum bounded degree k-vertex-connected subgraph problem. Spanning tree: there is an (1+1/(d-1))-approximation algorithm for the minimum bounded degree spanning tree problem. These approximation algorithms return solutions with smallest possible maximum degree, and the cost guarantee is obtained by comparing to the optimal cost when there are no degree constraints. This demonstrates that degree constraints can be incorporated into network design problems with metric costs.Our algorithms can be seen as a generalization of Christofides' algorithm for metric TSP. The main technical tool is a simplicity-preserving edge splitting-off operation, which is used to "short-cut" vertices with high degree while maintaining connectivity requirements and preserving simplicity of the solutions.