Minimum Labelling Spanning Tree problem
Many combinatorial optimization problems can be formulated on a graph where the possible solutions are spanning trees. These problems consist of finding spanning trees optimizing some measure and have been extensively studied in graph theory. Typical measures include the total length or the diameter of the tree. The minimum labeling spanning tree (MLST) problem is one of these problems. Many real-life combinatorial optimization problems belong to this class of problems and consequently there is a large and growing interest in both theoretical and practical aspects. For some of these problems there are polynomial-time algorithms, while most of them are NP-hard. Mainly, it means that it is not possible to guarantee that an exact solution to the problem can be found and one has to settle for heuristics and approximate solution approaches with performance guarantees.
In the MLST problem, we are given a graph with colored edges, and one seeks a spanning tree with the least number of colors. Such a model can represent many real-world problems in telecommunication networks, electric networks, and multimodal transportation networks, among others. For example, in communication networks, there are many different types of communication media, such as optic fiber, cable, microwave, telephone line and so on (Tanenbaum, 1989). A communication node may communicate with different nodes by choosing different types of communication medium. Given a set of communication network nodes, the problem is to find a spanning tree (a connected communication network) that uses as few types of communication lines as possible. This spanning tree will reduce the construction cost and the complexity of the network.
The MLST problem can be formulated as a network or graph problem. We are given a labeled connected undirected graph G = (V,E,L). The vertices represent communication nodes, the edges communication links and the labels communication type. Each edge in E is labeled or colored by a label or color in a finite set L that identifies the type of communication; different edges in the graph may have the same label. The objective is to find a spanning tree which uses the smallest number of different types of edges. Define LT to be the set of different labels of the edges in a spanning tree T. The labelling can be represented by a function fL: E ⇒ L for all edges e ∈ E or by a partition PL of the edge set; the sets of the partitions are those consisting of the edges with the same label or color.
For example, for telecommunication networks (and, more generally, any type of communication networks), managed by different and competing companies, the aim of each company is to ensure the service to each terminal node of the network whilst minimizing the cost (represented by connections managed by other companies). The telecommunication network is represented by a graph where each edge is assigned a set of colors and each color denotes a different company managing the edge (Voß et al., 2005). The aim is to find a spanning tree of the graph using the minimum number of colors, which means that all the terminal nodes are required to be covered by avoiding cycles and minimizing the overall number of different companies.
The minimum labelling spanning tree problem (MLSTP) is formally defined as follows. Given a labeled graph G = (V,E,L), find a spanning tree T of G such that |LT| is minimized, where LT is the set of labels used in T.
Figure 1: A sample graph and its optimal MLST solution.
Figure 1 shows an input graph and its optimal MLST solution. In contrast to the traditional minimum spanning tree (MST) problem, the MLST problem focuses on the uniqueness of a graph instead of the cost of a graph. The next section reports the literature review on the problem.
Literature review
In communications network design, it is often desirable to obtain a tree that is “most uniform” in some specified sense. Motivated by this observation, Chang and Leu (1997) introduced the minimum labelling spanning tree problem. They also proved that it is an NP-hard problem and provided a polynomial time heuristic, the maximum vertex covering algorithm (MVCA), to find (possibly sub-optimal) solutions. This heuristic begins with an empty graph. It then adds the label whose edges cover as many unvisited nodes as possible until all the nodes are covered. The heuristic solution is an arbitrary spanning tree of the resulting graph. However, with this version of MVCA, it is possible that although all the nodes of the graph are visited, it does not yield a connected graph and thus fails.
Krumke and Wirth (1998) proposed a corrected version of MVCA. This begins with an empty graph. Successively, it adds at random one label from those labels that minimize the number of connected components. The procedure continues until only one connected component is left, i.e. when only a connected subgraph is obtained. Krumke and Wirth (1998) proved that MVCA can yield a solution no greater than (1 + 2 log n) times optimal, where n is the total number of nodes. Later, Wan et al. (2002) obtained a better bound for the greedy algorithm introduced by Krumke and Wirth (1998). The algorithm was shown to be a (1 + log(n - 1))-approximation for any graph with n nodes (n > 1).
Brüggemann et al. (2003) used a different approach; they applied local search techniques based on the concept of j-switch neighbourhoods to a restricted version of the MLST problem. In addition, they proved a number of complexity results and showed that if each label appears at most twice in the input graph, the MLST problem is solvable in polynomial time.
Xiong et al. (2005b) derived tighter bounds than those proposed by Wan et al. (2002). For any graph with label frequency bounded by b, they showed that the worst-case bound of MVCA is the bth-harmonic number Hb:
Other heuristic approaches to the MLST problem are proposed in the literature. For example, Xiong et al. (2005a) presented a Genetic Algorithm (GA) to solve the MLST problem, outperforming MVCA in most cases.
Subsequently, Cerulli et al. (2005) applied the Pilot Method, a greedy heuristic developed by Duin and Voß (1999) and subsequently extended in (Voß et al., 2005), to the MLST problem. Considering different sets of instances of the MLST problem, Cerulli et al. (2005) compared this method with other metaheuristics (Reactive Tabu Search, Simulated Annealing, and an ad-hoc implementation of Variable Neighbourhood Search). Their Pilot Method obtained the best results in most of the cases. It generates high- quality solutions to the MLST problem, but running times are quite large (especially if the number of labels is high).
Xiong et al. (2006) implemented simplified versions of the Pilot Method of Cerulli et al. (2005), along with a Modified Genetic Algorithm (MGA) which obtained the best performance for the MLST problem in terms of solution quality and running time.
In (Consoli et al., 2008; 2009) a Greedy Randomized Adaptive Search Procedure, and dif- ferent versions of Variable Neighbourhood Search, were investigated. A comparison with the results provided by the best performing methods from the literature, the Pilot Method by Cerulli et al. (2005) and the Modified Genetic Algorithm by Xiong et al. (2006), showed that these heuristics based on GRASP and VNS obtained the best performance, producing high-quality solutions in short computational running times. Furthermore, a comparison with the results provided by an exact approach showed that these heuristics quickly obtain optimal or near-optimal solutions.
Test datasets for the MLST problem
The following link allows to download some instances of the minimum labelling spanning tree problem.
These are the instances used in the computations by the authors of (Consoli et al., 2008; 2009). They considered two different groups of datasets, including instances with a number of vertices, n, and a number of labels, l, from 20 up to 500. The number of edges, m, is obtained indirectly from the density d of edges whose values are chosen to be 0.8, 0.5, and 0.2. In particular, the first group of instances (Group 1) consists of small instances with the number of vertices equal to the number of labels. These values are chosen to be between 20 and 50 in steps of 10. The second group (Group 2) considers larger instances of the MLST problem with a fixed number of vertices n, from 100 to 500, and a number of labels l = 0.25 n, 0.5 n, n, 1.25 n.
References
Brüggemann, T., Monnot, J., Woeginger, G. J., 2003. Local search for the minimum label spanning tree problem with bounded colour classes. Operations Research Letters 31, 195-201.
Cerulli, R., Fink, A., Gentili, M., Voß, S., 2005. Metaheuristics comparison for the minimum labelling spanning tree problem. In: Golden, B., Raghavan, S., Wasil, E. (Eds.), The next wave in computing, optimization, and decision technologies. Springer-Verlag, Berlin, pp. 93-106.
Chang, R. S., Leu, S. J., 1997. The minimum labeling spanning trees. Information Processing Letters 63 (5), 277-282.
Duin, C., Voß, S., 1999. The pilot method: A strategy for heuristic repetition with applications to the Steiner problem in graphs. Networks 34 (3), 181-191.
Krumke, S. O., Wirth, H. C., 1998. On the minimum label spanning tree problem. Infor- mation Processing Letters 66 (2), 81-85.
Tanenbaum, A. S., 2003. Computer networks, 4th Edition. Prentice Hall, Englewood Cliffs, New Jersey.
Voß, S., Fink, A., Duin, C., 2005. Looking ahead with the pilot method. Annals of Operations Research 136, 285-302.
Voß, S., Martello, S., Osman, I. H., Roucairol, C., 1999. Meta-heuristics: Advances and trends in local search paradigms for optimization. Kluwer Academic Publishers, Norwell, MA.
Wan, Y., Chen, G., Xu, Y., 2002. A note on the minimum label spanning tree. Information Processing Letters 84, 99-101.
Xiong, Y., Golden, B., Wasil, E., 2005a. A one-parameter genetic algorithm for the minimum labeling spanning tree problem. IEEE Transactions on Evolutionary Computation 9 (1), 55-60.
Xiong, Y., Golden, B., Wasil, E., 2005b. Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem. Operations Research Letters 33 (1), 77-80.
Xiong, Y., Golden, B., Wasil, E., 2006. Improved heuristics for the minimum label spanning tree problem. IEEE Transactions on Evolutionary Computation 10 (6), 700-703.