Consider the following problem: Given a simple, strongly-connected, weighted gra
ID: 650103 • Letter: C
Question
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.
Explanation / Answer
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.