10
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Tony Huynh
    May 24, 2010 at 23:05
  • $\begingroup$ 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). $\endgroup$
    – Dave Pritchard
    May 25, 2010 at 6:58
  • $\begingroup$ 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? $\endgroup$
    – domotorp
    May 25, 2010 at 14:28
  • $\begingroup$ 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. $\endgroup$
    – Dave Pritchard
    May 26, 2010 at 12:17

1 Answer 1

Reset to default
2
$\begingroup$

Here are some nice lemmas that you can use: http://www.cs.elte.hu/egres/qp/egresqp-10-04.pdf

Dave pointed out my mistake, the subgraphs of spanning trees do not have to be trees. So I have no clue about the answer.

Espacially Problem 4 (or 10) seems promising. Take the graph from their construction such that all of its edges have a different color, suppose it has e edges. Then if we allow multigraphs, adding every edge with multiplicity 2n-2-e, all of a different color but same for each edge (thus in total we have 2n-2 colors) shows that your question solvable in P is NP-hard for multigraphs. Am I right? I would guess that with some further tricks you can make a simple graph from this for the variant you asked.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Will check out this paper when I pause travelling long enough. Due to forgetting "spanning" in the comment, I need to correct that actually the "rainbow union-of-2-spanning-trees" problem is in P even for multigraphs. I would be equally happy to resolve the "2 individually-rainbow spanning-trees" problem whether for simple or multigraphs. To reiterate, in all cases, the only trees I care about are spanning. $\endgroup$
    – Dave Pritchard
    May 26, 2010 at 22:16
  • $\begingroup$ Okay. I am still confused about the matroid M1, I do not think that it has a poly time computable rank function, since deciding the bases does not give an algorithm for deciding independent sets. Plus there is my above mentioned result that shows that it is NP-hard. $\endgroup$
    – domotorp
    May 27, 2010 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.