In graph G, every edge has a color. Rainbow spanning tree is a spanning tree where all edges have different colors. I want a polynomial algorithm to find such tree if exists any Anyone can help?
1 Answer
$\begingroup$
$\endgroup$
Boersma and Li [1] give a characterization of when an edge-colored graph contains a rainbow spanning tree. A polynomial time algorithm for your problem exists as the problem is equivalent to finding a common independent set of maximum cardinality in two matroids.
The problem of finding a spanning tree with as few different colors as possible is NP-hard, as shown in the same paper I believe.
[1] Hajo Broersma and Xueliang Li. Spanning trees with many or few colors in edge-colored graphs. Discuss. Math. Graph Theory, 17(2):259–269, 1997.