# Find a MST such that it's mostly red (original graph's edges are colored red and blue)

Consider the following problem: Given a simple, strongly-connected, weighted graph G=(V,E), of which every edge is colored either red or blue (in addition to having a numeric weight). Find an efficient algorithm to find an MST which is mostly red (meaning, has the most red edges possible).

I think this can be done in linear time, in O(n+m) complexity using either Kruskal or Prim's algorithms, but I can't find an algorithm to do that.

I thought about diving the edges into two groups - red and blue, and then running Kruskal's algorithm on the red edges first, and then if we still don't have |V|-1 edges in the MST we have so far, run Kruskal again on the blue edges. However, this algorithm doesn't solve the given problem since we might not end up with a tree, but rather with a forest (made up of two trees).

• Hint: If edge weights are unique, there is only one MST. If that is not the case, the only "decision space" Kruskal has is which edge of the same weight it picks first. It does always pick the same number of edges with a certain weight. So what happens if you pick always red if you have a choice? – Raphael Dec 3 '14 at 18:02
• @Raphael So your suggestion would be to sort the edges by their weight, and then for every two edges that have the same weight, have the red one before the blue one? If that's not what you meant, I'm not really sure how do I go about doing that then. – The_Ben Dec 3 '14 at 19:27
• Yes, that's what I meant. – Raphael Dec 4 '14 at 8:10

Hint: Add $\epsilon>0$ to the weight of all blue edges. (This is equivalent to the suggestion Raphael made in his comment.)