Hierarchies to Solve Constrained Connected Spanning Problems

Given a graph and a set of vertices, searching for a connected and minimum cost structure which spans the vertices is a classic problem. When no constraints are applied, the minimum cost spanning structure is a sub-graph corresponding to a tree. If all the vertices in the graph should be spanned the problem is referred to as minimum spanning tree (MST) construction and polynomial time algorithms exist to find these trees. On the contrary, if only a subset of vertices is concerned then the problem becomes NP-hard. The computation of partial minimum spanning trees is known as the Steiner problem in graphs. In some cases, constraints are present in the problem formulation: several constrained spanning and Steiner problems are known. Generally,only the tree-like spanning solutions were investigated. In this paper, we demonstrate that the cost optimal spanning structure in constrained situations is not necessarily a spanning tree. To find the optimal spanning structure, we propose the extension of the tree concept and we define the hierarchies. A hierarchy is obtained by a graph homomorphism from a tree to a given target graph which may refer vertices (and so edges) of the target graph several times. We prove that generally (including constrained spanning problems) the minimum cost connected structure spanning a set of vertices is a spanning hierarchy. To justify the introduction of spanning hierarchies, some spanning problems with various constraints are presented. The constrained spanning problems are frequently NP-hard and intensive research will be required to explore the properties of the optimal spanning hierarchies and to find exact and efficient heuristic algorithms to solve these newly formulated problems.