*(English)*Zbl 1046.90070

Summary: 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\u2a7e3$.

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\u2a7e3$, there exist instances for which some local optima are a factor of $r/2$ away from the global optimum.

##### MSC:

90C27 | Combinatorial optimization |

90C59 | Approximation methods and heuristics |

90C40 | Markov and semi-Markov decision processes |

05C85 | Graph algorithms (graph theory) |