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?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
Boersma and Li [1] give a characterization of when an edgecolored 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 NPhard, as shown in the same paper I believe. [1] Hajo Broersma and Xueliang Li. Spanning trees with many or few colors in edgecolored graphs. Discuss. Math. Graph Theory, 17(2):259–269, 1997. 

