I was asked the following question in an interview and I am unable to find an efficient solution.
Here is the problem:
We want to build a network and we are given n nodes and m edges. Edges are bidirectional and we know the cost of the edge. All the costs of the edges are hold in an array C, so C[i,j] which denotes the cost of the edge i-j. If nodes i,j are not connected then C[i,j] is infinite.
Now we also know that exactly K of the nodes are able to communicate wireless to other nodes which have also this property (for wireless transmission). To set up wireless technology to node i costs B[i]. So node i in order to use the ability of wireless transmission to node j this will costs B[i] to set up the wireless technology to node i and B[j] for j.
So the question is to find the minimum cost required to build the network where any two nodes i,j could communicate (there will be a path connecting them).
As path we mean that either there are edges that lead from node i to j or we can also use wireless transmission between nodes that support it.
It clear that it is asked for minimum spanning tree but the difficulty is that for example if we use wireless technology for node i,j and k then we add possible edges i-j,i-k,j-k but if we use only in i,j then we have only extra edge i-j so the edges depend on what node we choose to use for wireless transmission.
A simple example:
Let say we have 4 nodes and 3 edges C[1,2]=9 , C[1,3]=3 , C[3,4]=5 (other C[i,j] are infinite).
Nodes 2 and 3 support wireless technology with set up costs B[2]=2 and B[3]=1.
In this example the minimum cost would be: 16 = 8 (for edge 1-3) + 5 (for edge 3-4) + 2 (for set up cost 2) + 1 (for set up cost in node 3).
If we didn't use wireless technology in edge 2-3 then to make the network we should include edge 1-2 with cost 9 so total cost would be 9+8+5 = 22.
I am looking for an efficient algorithm for this kind of minimum spanning tree problem. Any help would be appreciated, thank you for your time!!
Solve the minimum spanning tree problem first, that gives you an incumbent answer to try beat.
Now, create another graph the same as the original graph, add a new node to this network. Connect all of the K nodes to this new node with edge weight equal to B[i]. This edge represents the cost of adding wireless to node i. Now find the minimum spanning tree of the new graph. Nodes can now connect through this node as "wifi".
(I'm assuming that they tell you which K nodes support wifi, and not that you must choose K of the N nodes, otherwise you will have problems if this new minimum spanning tree has more than K connections to the new node)).