Local search for the minimum label spanning tree problem with bounded color classes

In the Minimum Label Spanning Tree problem, the input consists of an edge-colored undirected graph, and the goal is to find a spanning tree with the minimum number of different colors. We investigate the special case where every color appears at most r times in the input graph. This special case is polynomially solvable for r = 2, and NP- and APX-complete for any fixed r greater than or equal to 3. We analyze local search algorithms that are allowed to switch up to k of the colors used in a feasible solution. We show that for k = 2 any local optimum yields an (r + 1)/2-approximation of the global optimum, and that this bound is tight. For every k greater than or equal to 3, there exist instances for which some local optima are a factor of r/2 away from the global optimum. (C) 2003 Published by Elsevier Science B.V.