Finding a spanning tree using exactly k red edges in a graph with edges colored by red/blue in linear time

Question

Given a graph G with red and blue edges and a constant K, devise a deterministic, linear time algorithm that finds a spanning tree of G with exactly K red edges (or returns False if such a spanning tree does not exist).

What we have done so far:

Let every red edge have weight of -1 and every blue edge have weight of 0.

Find a minimum spanning tree (using a standard linear time algorithm). So, we have a spanning tree T with minimal weight, meaning we used as many red edges as we can because red edges will only decrease the weight.

If there are less than K red edges in T, we return False.

If there are exactly K red edges, we are done, T is the answer.

If there are more than K red edges, we need to replace them with blue ones.

This is our problem, how do we do that in linear time?

Every blue edge added will create a cycle, so removing one red edge from the cycle will work but how can we ensue linearity in this way? Is this even a good approach?

Answer 1

HINTS

You can do this in linear time using two passes of Prim's algorithm. (Usually Prim's algorithm is not linear time, but when you only have two types of edge you do not need to spend time sorting edges).

Pass 1

In the first pass follow blue edges before red edges and mark any red edges that you are forced to take.

If you mark C edges in this process then we know that there must be at least C red edges in any spanning tree solution, so if C>K, it is impossible.

Pass 2

Suppose we have found C ( < K ) marked edges in the first pass.

In the second pass follow red edges before blue, until the total number of additional red edges reaches K-C. In the second pass you are also allowed to follow the red edges marked in the first pass (and these do not count towards your total).

If your additional red edges does not reach K-C then it is impossible.