# Degree-Constrained Steiner Problem in Graphs with Capacity Constraints
## 1 Introduction  
In the Steiner problem in graphs, a given subset of nodes must be spanned at a minimum cost. Without any constraint, the optimum is a partial minimum spanning tree (PMST) or a Steiner tree. In some applications, additional constraints must be satisfied. Various constrained spanning problems and Steiner problems have been analyzed in graphs (cf. examples in [1; 2; 3]). We are interested in the degree-constrained Steiner problem. Each node \(v\in V\) of the graph \(G=(V,E)\) is assigned a positive integer value \(D(v)\) which represents the maximum degree of the node in any spanning structure (for example, in the spanning trees).  
Often, _budget_-type degree constraints are assumed. For instance, when the bounds are uniform and equal to two, only paths can be used to span the nodes (the problem corresponds to the well-known traveling salesman problem, and the solution does not always exist). Having different bounds, it is not always possible to span the nodes using trees that meet the degree constraints. Degree-constrained spanning tree and Steiner tree problems are NP-hard. Moreover, they can not be approximated by a constant factor if the degrees correspond to budgets [4]. In the case of a limited budget of the nodes, the minimum cost solution is a tree: it contains a node at most once.  
The motivation of the recent study is the definition and the analysis of the exact solution of the minimum cost degree-constrained partial spanning in the cases of limited node capacities. _Supposing capacity-like constraints on the node degrees, the optimum may be different from a tree_ (we suppose that a node can participate multiple times in the coverage and the degree of each occurrence is limited by the given capacity). In these cases, a spanning hierarchy corresponds to the optimum. The next section provides formal definitions. Themain advantages of the hierarchies in the discussed Steiner problems are: (1) In some cases, Steiner hierarchies exist but Steiner trees that meet the constraints do not exist; (2) Even if Steiner trees respecting the degree constraints exist, in some cases, a hierarchy of least cost can be constructed.  
Capacity-like constraints can be found in transparent optical networks where the duplication capacity of the optical switches is limited. If there is no node/switch capable of duplicating or splitting the incoming light, only light paths can be used for optical routing. The optical multicast route using the cross-connect capacity of the switches can visit a switch several times and can be different from a partial spanning tree [5]. The reader can learn more about the specifics of optical networks in [6].  
To the best of our knowledge, our paper is the first to analyze the solution for the minimum Steiner problem under bounded degree capacities in the nodes.  
In the paper, we propose a quick presentation of the well-known degree-constrained Steiner tree problems (cf. Section 2). The related definitions and the used notations can be found in Section 3. The necessary and sufficient conditions for a solution to exist are formulated in Section 4. An ILP-based exact computation (cf. Section 5) is also proposed. The tree-based and hierarchy-based solutions are compared in Section 7 followed by the conclusions.