# Degree-Constrained Steiner Problem in Graphs with Capacity Constraints
## 2 Previous Work  
The minimum Steiner tree computation is largely studied in the literature. Several hundred papers can be found on the approximations and methods for solving this NP-hard problem and its variants. The 11 th DIMACS Implementation Challenge as well as the PACE 2018 ChallengeA provide important summaries of the evolution of the treatments (methods and new computational results) of the Steiner problem. A large survey is presented in [7]. A recent paper [8] analyzes integer programming and mixed-integer programming formulations for the optimization problems that are based on induced connectivity. It provides some conditions for LP-relaxations of both the maximum weight connected sub-graph and the Steiner tree problem to be tight. Local search algorithms are used for improving the computed Steiner trees by replacing sub-trees with advantageous structures in [9]. The proposed methods outperform the known local search algorithms. The same authors propose a method based on supervised learning to produce a quasi-optimal Steiner tree in [10]. Artificial Intelligence is a good candidate for finding efficient patterns in the construction of spanning structures. Another learning-based solution can be found in [11] to solve the clustered Steiner tree problem (which is a recently introduced NP-hard problem for efficient multicast routing in a decentralized clustering network architecture). The degree-constrained spanning tree problem in graphs is one of the NP-hard problems cited in [12]. While the degree-constrained spanning problem has been intensively studied, a few papers talk about the degree-constrained Steiner problem. An extensive study can be found in [13]. In [14], the authors argue the particular interest of this problem with the limited capability of switches in high-speed networks to realize multicast routing. It is not always possible to span the nodes using trees while respecting the degree constraints (cf. [14]). The general case in which the bounds are different is NP-hard using a reduction to the traveling salesman problem (cf. [2]). The degree-constrained minimum cost sub-graph problems are NP-hard. Polynomial-time algorithms computing good approximations are needed. The first approximation scheme is proposed in [15]. In [4], the problem is presented as a generic bi-criteria optimization problem \((A,B,S)\) where the first objective \(A\) corresponds to the respect of the budget constraints, the second (\(B\)) is the minimization of the cost, and \(S\) describes the class of the solution. The investigated classes (as usual) are spanning trees, Steiner trees, and generalized Steiner trees. The authors prove the hardness of the proposed optimizations. They demonstrate that the partial spanning problem with non-uniform bounds cannot be approximated with \((2-\epsilon,\rho)\) for any \(\epsilon>0\) and \(\rho>1\)[4]. Paper [16] shows a quasi-polynomial time approximation algorithm computing a Steiner tree in a graph with nodes. The tree is of maximum degree \(O(B+logn)\), and its cost is within a constant factor of a minimum Steiner tree whose maximum degree is bounded by \(B\). For fault-tolerant networking, ref. [17] presents a variant, the minimum degree bounded Steiner network problem, where the minimum-cost Steiner network that satisfies all the degree bounds is required. A Steiner network is a graph with at least \(r(u,v)\) edge-disjoint paths between nodes in all pairs of nodes \(u\), \(v\) (\(r(u,v)\) is the connectivity requirement for the network). The paper proposes a polynomial time approximation algorithm that returns a Steiner forest or a Steiner network of cost at most twice the optimal cost solution when the degree violation at each node is bounded. [PERSON] et al. also present algorithmic and hardness results on the survivable network design problem with degree constraints; among others, there is a constant factor approximation algorithm applicable for many degree-constrained network design problems, including the minimum bounded degree Steiner forest problem [18].