4

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?

Shubham Mittal
  • 1,545
  • 18
  • 21
Rachel Bernouli
  • 225
  • 2
  • 9
  • 1
    It is not clear whether you are trying to find a minimum spanning tree with K red edges, or any spanning tree with K red edges, or a spanning tree which is minimal among those spanning trees which have K red edges. – Tyler Durden Feb 11 '14 at 16:21
  • Just found out it can be solved using edge contraction...not sure how to use it tho.. – Rachel Bernouli Feb 11 '14 at 16:38
  • @Tyler: To me it's pretty clear: "finds a spanning tree of G with exactly K red edges" nothing said about minimality – Niklas B. Feb 11 '14 at 16:52
  • @RachelBernouli - In your question, "Find a minimum spanning tree (using a standard linear time algorithm)." which linear time algorithm are you referring to ? – Shubham Mittal Aug 01 '16 at 19:48

1 Answers1

3

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.

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
  • 1
    Nice one, I was about to propose a very similar idea in conjunction with Kruskal: First run it with `e = B + R` (B = blue edges, R = red edges). Let X be the edges in R that were used in that run. Now run Kruskal again with `e = X + (R \ X) + B` and now stop adding red edges as soon as you have selected `k` of them. – Niklas B. Feb 11 '14 at 16:51
  • @NiklasB. That sounds just as good. I'll upvote if you put it as an answer :) – Peter de Rivaz Feb 11 '14 at 17:40
  • Could you please explain further? Prims algorithm works on weighted graphs, so what do you mean by goes for blue first?.. – Rachel Bernouli Feb 12 '14 at 00:27
  • I mean to use the same approach that you did (e.g. of assigning weight 0 to blue edges, and weight 1 to red edges). Once you have done this, Prim's algorithm will always add blue edges in preference to red edges when possible. – Peter de Rivaz Feb 12 '14 at 08:12
  • @NiklasB. When you run Kruskal, won't it use union-find and lead to a O(V logV) solution ? OP is asking for a linear solution. – Shubham Mittal Aug 01 '16 at 19:46
  • @Shubham depending on practical considerations, maybe the inverse ackermann factor can be tolerated – Niklas B. Aug 02 '16 at 05:58