Degree-Constrained Steiner Problem in Graphs with Capacity Constraints

The degree-constrained Steiner problem in graphs is well known in the literature. In an undirected graph, positive integer degree bounds are associated with nodes and positive costs with the edges. The goal is to find the minimum cost tree spanning a given node set while respecting the degree bounds. As it is known, finding a tree satisfying the constraints is not always possible. The problem differs when the nodes can participate multiple times in the coverage and the constraints represent a limited degree (a capacity) for each occurrence of the nodes. The optimum corresponds to a graph-related structure, i.e., to a hierarchy. Finding the solution to this particular Steiner problem is NP-hard. We investigate the conditions of its existence and its exact computation. The gain of the hierarchies is demonstrated by solving ILPs to compute hierarchies and trees. The advantages of the spanning hierarchies are conclusive: (1) spanning hierarchies can be found in some cases where spanning trees matching the degree constraints do not exist; (2) the cost of the hierarchy can be lower even if the Steiner tree satisfying the constraints exists.