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).

Please advise.

  • 4
    $\begingroup$ 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? $\endgroup$ – Raphael Dec 3 '14 at 18:02
  • $\begingroup$ @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. $\endgroup$ – The_Ben Dec 3 '14 at 19:27
  • $\begingroup$ Yes, that's what I meant. $\endgroup$ – 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.)


Your problem is ambiguous. What is the first to be optimized? the number of red edges or the tree cost? If the tree cost must be the same as an MST of the uncolored graph, Yuval's solution is correct (equivalently when sorting the edges in Kruskal algorithm, break tie by their color). If you want to find the minimized tree cost among all spanning trees with the most possible red edges, your algorithm is correct. For your question, if the algorithm cannot find a tree, there is no MST, i.e., the graph is not connected. BTW, the time complexity is not linear.

  • $\begingroup$ Thanks for the answer. However, my algorithm isn't always correct. The algorithm should take the most red edges possible, but if you have to take a blue edge to make an MST, that's alright too. $\endgroup$ – The_Ben Dec 4 '14 at 8:00

Approach 1: Use a disjoint set structure, every vertex will be a set, then connect all the vertices with the red edges first, and then add the blue edges. Linear time.

Approach 2: Second approach, weight of red is 0 and weight of blue is 1. Run Prim algorithm. it is linear because you don't have to sort the edges.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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