# Degree-Constrained Steiner Problem in Graphs with Capacity Constraints
## 5 Computation of an Exact Solution
### Reconstruction of an Optimal Hierarchy  
The variable \(x(n,m)\) indicates how many times the arc \((n,m)\in A^{\prime\prime}\) is used in the directed solution. At first, a minimal Steiner arborescence \(T^{\prime\prime}\) rooted at \(s\) of the solution \(H=(T^{\prime\prime},h,G^{\prime\prime})\) can be built. If the number of occurrences of some arcs is different from one, several arborescences may correspond to the image. We let \(i(n)=\sum_{m\in\Gamma^{-}(n)}x(n,m)\) and \(o(n)=\sum_{m\in\Gamma^{+}(n)}x(n,m)\) be the number of incoming and outgoing arcs of the node \(n\), respectively. In an arborescence, each node occurrence has one and only one predecessor (except the source). The node \(n\) must be duplicated \(i(n)\) times in the arborescense (the source must be duplicated \(i(s)+1\) times). With each occurrence of \(n\), one incoming arc can be associated. The successors can be distributed arbitrarily among the occurrences of \(n\) while respecting the degree constraints: each occurrence of \(n\) can have at most \(D(n)-1\) successors. For instance, all occurrences of \(n\) except one can have the maximal degree \(D(n)\). The outline of the construction is as follows. 1. For each node \(n\), a set of successors is created from values \(x(n,m)\). (For each node \(m\in\Gamma^{+}(n)\), \(x(n,m)\) occurrences of \(m\) should be added to the set of successors of \(n\)). Each node occurrence is labeled by its identifier in \(G\). 2. The construction of the labeled tree \(T^{\prime\prime}\) starts at the source node \(s\). 3. The first occurrence of the source has no predecessor. If the number of successors is greater than \(D(s)\), the first occurrence of the source has \(D(s)\) successors. The remaining successors are associated with the other source occurrences. 4. The nodes are processed recursively. We let \(n\) be the current node. 1. The successors (using the corresponding outgoing arcs) are distributed among the occurrences of \(n\). All occurrences except one have the maximal degree \(D(n)\). (the successors can be distributed between the occurrences of \(n\) such that \(D(n)-1\) successors are connected to the first \(|\Gamma^{+}(n)|-1\) occurrences of \(n\)). The remaining successors are associated with the last occurrence. 2. For each successor node, a sub-tree is built recursively. 3. If the current node \(n\) is a leaf, there is nothing to do. The result of the given construction is a directed labeled tree \(T^{\prime\prime}=(V_{T},A_{T})\). Proof. : For each node occurrence, a set of successors is connected using an arc from the node to each successor. Each successor is a distinct node occurrence. There, in the no cycle, a node occurrence and its successors form a directed sub-tree. In the tree, the nodes are labeled. Recursively, a successor is the root of a subsequent sub-tree. Trivially, \(T^{\prime\prime}\) is a labeled directed tree. **Theorem 2**. : _Omitting the direction of the arcs of \(T^{\prime\prime}=(V_{T},A_{T})\), an undirected, labeled tree \(T=(V_{T},E_{T})\) is obtained that corresponds to a DCMStH._  
Proof. : The computed image is a connected sub-graph in \(G\) and covers the node set \(M\). The tree construction processes each node of the image, and each node in \(M\) is associated with at least one node of \(T^{\prime\prime}\) (\(M\subseteq V_{T}\)). The node set of \(V_{T}\) is the same in \(T^{\prime\prime}\) and \(T\) with the same labels. The labels of nodes in \(T\) correspond to a node in \(G\) and the association can be given by \(h\). The hierarchy \(H=(T,h,G)\) spans the node set \(M\). By construction, the nodes in \(T^{\prime\prime}\) and \(T\) respect the degree constraints (a node occurrence of the node \(n\in V^{\prime\prime}\) has at most \(D(n)\) neighbors). So, \(H\) is a degree-constrained hierarchy spanning \(M\). It is with minimum cost. Its cost is the sum of the cost of the edge occurrences belonging to it. An edge \(\{m,n\}\) is present \(x(m,n)+x(n,m)\) times in \(H\) (in tree \(T\)).