Supposes youre a consultant for the networking company CluNe

Supposes you\'re a consultant for the networking company CluNet, and they have the following problem. The network that they\'re currently working on is modeled by a connected graph G = (V,E) with n nodes. each edge e is a fiber-optic cable that is owned by one of two companies - creatively named X and Y - and leased to CluNet.

Their plan is to choose a spanning tree T of G and upgrade the links corresponding to the edges of T. Their business relations people have already concluded an agreement with companies X and Y stipulating a number k so that in the tree T that is chosen, k of the edges will be owned by X and n-k-1of the edges will be owned by Y.

CluNet management now faces the following problem. It is not at all clear to them whether there even exists a spanning tree T meeting these conditions, or how to find one if it exist. So this is the problem they put to you: Give a polynomial-time algorithm that takes G with each edge labeld X or Y and either (i) returns a spanning tree with exactly k edges labeled X or (ii) reports correctly that no such tree exists.

Solution

This problem is just modification of prim\'s algorithm and famous problem. You can modify this problem to -

Find minimum spanning tree containing edges of blue and red color, you need to find such spanning tree which have k red color and n - k - 1 blue color. So basically assign all the blue edges to weight having 0 and red edges to 1. Then use prims algorithm and during creation of spanning tree count the number of red edges you are forced to take to build the tree. Let countRed is that number.

If countRed is > k then there is no such possible spanning tree.

if it is equal to k then thats your solution.

if it is less than k then do this -

assign all the red edges of weight 0 and blue edges of weight 1 then do prim\'s algorithm . Now start building spanning tree. If count of red egdes is less than k and there is no more edge to process(or we have our spanning tree) then there is no solution else If the count of red edges reaches k then reverse the weight of all the unprocessed edges basically change weight of red to 0 and blue to 1. And process the remaining edges. This is your solution.

If you have any doubt regarding that you can ask me.