# Degree-Constrained Minimum Spanning Hierarchies in Graphs
## 1 Introduction  
It is important to cover node sets in graphs with minimum cost in several domains, for instance, for efficient broadcast/multicast communications in networks. The subgraph that spans the set of nodes with minimum cost is a minimum spanning tree (MST), and several polynomial-time algorithms to compute it are known. The partial spanning with minimum cost (the Steiner problem in graphs) is NP-hard. Some applications must meet additional constraints. We are interested in the degree-constrained spanning 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 \(v\) in any spanning structure. This degree is potentially different from the degree \(d(v)\) of \(v\in V\) (\(D(v)\leq d(v)\)). In the literature, proposals can be found to span the node set of a graph adhering to _budget_ type degree bounds [1; 2]. In these problems, nodes have limited budgets and cannot exceed the given limits in the spanning structures (in the spanning trees). Degree Constrained Minimum Spanning Tree (DCMST) problems are hard to solve, and unfortunately, constant factor approximations do not exist for them [3].  
Degree bound does not always correspond to a definitive budget but to a momentary limited _capacity_. For example, in optical networks, the capacity of duplication of the switches may be limited for each incoming light, but a wavelength can pass through a switch many times (cf. [4]). As a result, the optical broadcast/multicast route may be different from a spanning tree. In [5], a special walk returning to some nodes is proposed when spanning trees are impossible due to the absence of nodes having a degree bound greater than two. If the constraints can be greater than two, branching nodes are possible, and the spanning structure could be a hierarchy crossing certain nodes several times. For the case of homogeneous capacity constraints, a hierarchy-based optimum and its approximation have been proposed in [6]. The analysis of this NP-hard problem shows that this kind of solution still exists and can be approximated. The most important results of the related work can be found in Section 3.  
Here, we propose the analysis of cases presenting heterogeneous momentary capacity constraints.  
We are studying the following questions: In which cases does the solution exist? How can the optimum be calculated? Can it be approximated?  
As in the case of homogeneous capacity bounds, the optimal solution to the problem is a _hierarchy_. As a new result, we formulate necessary and sufficient conditions for its existence. The problem is NP-hard, and we highlight that, in some cases, the optimal solution can be approximated. We propose a special heuristic algorithm for this. In the following section, we present the definition of hierarchies. Section 3 offers a quick overview of DCMST issues, followed by the formulation of capacity-constrained spanning problems. The necessary and sufficient conditions for a solution to exist are formulated in Section 4. An ILP-based exact computation (cf. Section 5.1) and a heuristic algorithm (cf. Section 5.2) are also proposed. Section 6 presents some approximations. Performance is compared in Section 7.