Solving Connected Graphs with Algorithm: K Blue/Red Edges

[frank_buf@yahoo]

Homework Statement

Given a connected graph G = (V,E). Let n = |V |. Each edge in G is already colored
with either RED or BLUE. Devise an efficient (i.e. polynomial-time) algorithm which, given an integer k,
1 <= k <= n − 1, either (a) returns a spanning tree with k BLUE edges and n − 1 − k RED edges, or (b)
reports correctly that no such tree exists.

Homework Equations

The Attempt at a Solution

 

[berkeman]

Welcome to the PF, Frank. You need to show us all of your work and thoughts on this problem before we can help you. Why did you not fill in #2 and #2 in our Homework Posting Template? What are the relevant concepts that we should use in trying to help you figure out how to solve this question?

 

[piercas]

One possible solution to this problem is to use a modified version of Kruskal's algorithm. This algorithm is commonly used for finding minimum spanning trees in a graph, but it can also be adapted to solve this problem.

First, we sort the edges of the graph G in increasing order of weight. Then, we start with an empty spanning tree T and add edges to it one by one, always choosing the next smallest edge in the sorted list. However, we also keep track of the number of BLUE edges that have been added to T. If at any point, the number of BLUE edges in T exceeds k, we stop the algorithm and report that no spanning tree with k BLUE edges exists in G. Otherwise, once we have added n-1-k RED edges, we have a spanning tree with k BLUE edges and n-1-k RED edges, and we can stop the algorithm and return T as the solution.

This algorithm runs in polynomial time, as the sorting step can be done in O(|E|log|E|) time and the loop that adds edges to the spanning tree runs in O(|E|) time. Therefore, the overall time complexity is O(|E|log|E|), which is polynomial in the size of the input.

Another possible solution is to use a dynamic programming approach. We can define a function f(i, j) that represents the minimum weight of a spanning tree with exactly i BLUE edges and j RED edges. We can then use this function to recursively calculate the minimum weight of a spanning tree with k BLUE edges and n-1-k RED edges.

We can start with f(0,0) = 0, as an empty spanning tree has no weight. Then, for each edge (u,v) in G, we can consider two cases: either the edge is BLUE or RED. If it is BLUE, we add its weight to f(i+1,j), where i is the number of BLUE edges in the current spanning tree and j is the number of RED edges. If it is RED, we add its weight to f(i,j+1). We can then take the minimum of these two values and continue recursively until we reach f(k,n-1-k), which will give us the minimum weight of a spanning tree with k BLUE edges and n-1-k RED edges.

This approach also runs in polynomial time, as we only need to consider each edge once and the number of possible combinations of i and