# Degree-Constrained Steiner Problem in Graphs with Capacity Constraints
## 3 Notations and Definitions
### Problem Formulation  
In this paper, we suppose a simple graph \(G=(V,E)\) with positive costs. A positive integer value \(D(v)\) is associated with any node \(v\in V\) and considered as the degree bound of \(v\). **Definition 1** (Budget-type degree bound). : _The number of the neighboring nodes of \(v\) in any coverage can not exceed the degree bound \(D(v)\)._  
**Definition 2** (Capacity-type degree bound). : _The number of the neighboring nodes of each occurrence of \(v\) in any coverage can not exceed the degree bound \(D(v)\)._  
**Definition 3** (Spanning structure). : _It is a structure spanning the node set \(M\subseteq V\) that contains at least a walk between between the nodes of an arbitrary node pair of \(M\)._  
A generalization of the tree concept can be based on the graph homomorphism. The homomorphic mapping of the nodes of a tree \(T\) to nodes of a graph \(G\) defines a non-elementary tree in \(G\). **Definition 4** (Hierarchy). : _We let \(T=(P,F)\) be a tree. We let \(h:P\to V\) be a homomorphic function that associates node \(v\in V\) to each node \(p\in P\). Application \((T,h,G)\) defines a hierarchy in \(G\)._  
**Definition 5** (Image of a hierarchy). : _The sub-graph defined by the set of nodes and edges in \(G\) associated by \(h\) to \(T\) is the image of the hierarchy._  
The definitions in digraphs are also trivial. **Problem 1** (Budget-type degree-constrained Steiner tree problem). : _The integer value \(D(v)\) associated with any node \(v\in V\) is a budget. Given a subset \(M\subseteq V\) of nodes, we find a partial spanning tree in which the degree of any node \(v\) is at most \(D(v)\) and the tree cost is minimum._  
**Problem 2** (Capacity-type degree-constrained Steiner problem). : _The integer value \(D(v)\) associated with any node \(v\in V\) represents a capacity. Given a subset \(M\subseteq V\) of nodes, we find a \begin{table}
\begin{tabular}{l l} \hline \(G=(V,E)\) & : undirected graph given by node set \(V\) and edge set \(E\) \\ \(\{v,w\}\in E\) & : edge between nodes \(v\) and \(w\) \\ \(c(v,w)\) & : cost associated with the edge \(\{v,w\}\) \\ \(d(v)\) & : degree of the node \(v\) \\ \(D(v)\) & : degree bound of \(v\) (positive integer) \\ \(M\subseteq V\) & : the set of nodes to cover \\ \(V_{m}\subseteq V\) & : the subset of nodes with degree bound \(m\) \\ \(v^{l}\) & : \(i^{th}\) occurrence of \(v\in V\) in a hierarchy \\ \(G_{A}=(V,A)\) & : directed graph, equivalent to \(G\), two arcs \((v,x)\in A\) and \\  & \((w,v)\in A\) correspond to the edge \(\{v,w\}\in E\) of \(G\) \\ \(T=(P,F)\) & : tree with node set \(P\) and edge set \(F\) \\ \(H=(T,h,G)\) & : hierarchy defined by a homomorphic function \(h\) \\  & between tree \(T\) and graph \(G\) \\ \(\Theta(v)\) & : the set of nodes in \(P\) (in \(T\)) corresponding to \(v\in V\) \\ \(P_{m}\subseteq P\) & : the subset of nodes with degree \(m\) in the tree \\ \(AdjN(v)\) & : the set of adjacent nodes of the node \(v\) \\ \(AdjA^{+}(v)\) & : the set of incoming arcs at the node \(v\) in \(G_{A}\) \\ \(AdjA^{-}(v)\) & : the set of outgoing arcs at the node \(v\) in \(G_{A}\) \\ \(\Gamma^{-}(v)\) & : the set of predecessor nodes at the node \(v\) in \(G_{A}\) \\ \(\Gamma^{+}(v)\) & : the set of successor nodes at the node \(v\) in \(G_{A}\) \\ \hline \end{tabular}
\end{table} 
Table 1: Notations used in the paper. spanning structure such that the degree of any occurrence of \(v\) is at most \(D(v)\) in the structure and its cost is minimum._  
**Property 1**: _A spanning structure of \(M\subseteq V\) in \(G\) can be given by a homomorphism-based triplet \((S,h,G)\) such that all nodes in \(M\) are associated by \(h\) with at least one node of \(S\) and \(S\) is a connected graph._  
**Proof. ** All nodes in \(M\) must be covered, and so they must be associated with at least one node in \(S\). In a spanning structure, every pair of nodes of \(M\) must be connected by at least a walk. If \(S\) is not connected, there are node pairs without connection between them. Therefore, \(S\) must be connected.