# Degree-Constrained Minimum Spanning Hierarchies in Graphs
## 5 Algorithm Design
### Exact Solution
#### 5.1.3 Computation of the Image of the Solution  
In the next step, a valued, directed image of the DCMSH is computed in the digraph. Integer values are associated with the arcs indicating the number of transited flows. The set of arcs with non-zero flows determines the image. Note that the number of flows is not equal to the number of occurrences of the arc in the directed DCMSH.  
_ILP variables:_  
\(x(m,n)\): Integer variable. It is equal to the number of occurrences of arc \((m,n)\) in the resulted hierarchy.  
\(F(m,n)\): Commodity flow variable. It denotes the quantity of flow transiting on arc \((m,n)\).  
_Objective:_  
The cost of the image must be minimized.  
\[Minimize\sum_{m\in V}\sum_{n\in\Gamma^{+}_{m}}x(m,n)\cdot C(m,n). \tag{1}\]  
The values associated with the arcs indicate the number of incoming/outgoing arcs in the DCMSH. In an optimal hierarchy, there is a strictly minimal number of occurrences of any node. In our directed model, the number of occurrences of a non-source node is equal to the number of its predecessors. If there are multiple occurrences of the source node, the first one has no predecessor. Respecting the constraints, the number of occurrences must be sufficient to connect the successor nodes by the outgoing arcs. The degree constraints can be formulated as follows. At the arbitrarily selected source \(s\), there are returns if and only if the degree \(D(s)\) is not sufficient to be the start point of the outgoing arcs:  
\[\sum_{n\in\Gamma^{+}_{s}}x(s,n)\leq D(s)+(D(s)-1)\cdot\sum_{n\in\Gamma^{-}_{s }}x(n,s). \tag{2}\]Especially, if \(D(s)=1\), \(\Gamma_{s}^{-}\) is empty and there is only one outgoing arc.  
For an arbitrary non-source node \(m\), each occurrence of \(m\) can be the start point of at most \(D(m)-1\) outgoing messages:  
\[\sum_{n\in\Gamma_{m}^{+}}x(m,n)\leq(D(m)-1)\cdot\sum_{n\in\Gamma_{m}^{-}}x(n,m )\qquad\forall m\in V\setminus\{s\}. \tag{3}\]  
Trivially, for nodes in \(V_{1}\), no outgoing arc is used.  
The following lower bounds are not necessary but practical.  
At the source:  
\[\sum_{n\in\Gamma_{s}^{+}}x(s,n)>D(s)+(D(s)-1)\cdot(\sum_{n\in\Gamma_{s}^{-}}x(n,s)-1). \tag{4}\]  
In a non-source node \(m\) with degree bound \(D(m)>1\):  
\[\sum_{n\in\Gamma_{m}^{+}}x(m,n)>(D(m)-1)\cdot(\sum_{n\in\Gamma_{m}^{-}}x(n,m)- 1)\qquad\forall m\in V\setminus\{s\},D(m)\
eq 1. \tag{5}\]  
Every node except the source has a predecessor in the hierarchy. This condition guarantees the full coverage as follows.  
\[\sum_{n\in\Gamma_{m}^{+}}x(n,m)\geq 1\qquad\forall m\in V\setminus\{s\}. \tag{6}\]  
Full coverage does not mean full connectivity. Flows can be used to guarantee the connectivity. The arbitrary source is the start point of one flow per destination. (the destinations are the other \(|V|-1\) nodes). We have  
\[\sum_{n\in\Gamma_{s}^{+}}F(s,n)=|V|-1. \tag{7}\]  
Each non-source node is the destination of one and only one flow. We require  
\[\sum_{n\in\Gamma_{m}^{+}}F(m,n)=\sum_{n\in\Gamma_{m}^{-}}F(n,m)-1\qquad\forall m \in V\setminus\{s\}. \tag{8}\]  
The conditions of flow transit by occurrences of arcs are as follows.  
\[F(m,n)=0\qquad\forall(m,n)\in A\text{ if }\;x(m,n)=0, \tag{9}\] \[F(m,n)\geq x(m,n)\qquad\forall(m,n)\in A\text{ if }\;x(m,n)>0. \tag{10}\]  
If an arc does not belong to the solution, it does not carry any flow. Moreover, each arc should carry a non-zero flow if it belongs to the DCMSH, and the value of this flow must not be less than the number of occurrences of the arc.  
The number of occurrences of an edge in a DCMSH (and the number of occurrences of an arc in the directed model) is limited:  
\[x(n,m)\leq EB\qquad\forall m,n\in V. \tag{11}\]  
The upper bound \(EB\) can be calculated in advance.  
Remember, solving our linear program does not give a DCMSH but its image. Figure 5c illustrates the valued image of the solution in our example. A last phase is needed to construct an optimal \"non-elementary tree\" from its image.