# Finding Two Rainbow Spanning Trees

Suppose we have a graph whose edges are coloured. It's not necessarily a proper colouring: a given node may have 0, 1, or several incident edges of a given colour.

Is the following problem NP-complete? Determine whether there are two edge-disjoint spanning trees, such that in each individual tree, no colour appears twice.

I am curious because the variant "determine whether there are two edge-disjoint spanning trees, such that in the union of the trees, no colour appears twice" is solvable in polynomial time, for example using matroid theory.

• I can see how to find one rainbow spanning tree using matroid intersection. Can you say a bit more about how to find two disjoint spanning trees whose union is rainbow? – Tony Huynh May 24 '10 at 23:05
• What I had in mind is to use matroid union and intersection. First, take the matroid union of the graphic matroid with itself; this yields another matroid M1 whose bases are those edge sets which are partitionable into two trees. Second, consider the partition matroid M2 whose parts are the colour classes. Now use matroid intersection on M1 and M2: what we want to know is whether the largest common independent set has size 2(|V|-1). – Dave Pritchard May 25 '10 at 6:58
• Btw, I might be wrong, but the rank function of M1 seems to be NP-hard to compute (see problem 10 in my answer), so I do not see why you could solve the problem in P. Where am I mistaken? – domotorp May 25 '10 at 14:28
• Sorry I should mis-spoke; M1 is the matroid whose bases are those edge sets which are partitionable into two spanning trees. Schrijver's book sections 51.4, 42.3 talks about polynomial-time algorithms for this (corrected) version. – Dave Pritchard May 26 '10 at 12:17