# Show that the Minimum spanning tree Reduce Algorithm runs in O(E) on sparse graphs

This is a problem from CLRS 23-2 that I'm trying to solve. The problem assumes that given graph G is very sparse connected. It wants to improve further over Prim's algorithm $O(E + V \lg V)$. The idea is to contract the graph, i.e. collapse two or more nodes into one node. So each reduction will reduce the graph by at least half nodes. The question is to come up with implementation such that time complexity of MST-REDUCE is $O(E)$. This uses set operations. MakeSet, Union and Find-Set. I've annotated my analysis in the picture along with algorithm. I'm thinking to implement the set as linked list here. So my make-set and find-set are $O(1)$. But Union sucks: $O(V)$. Since we are doing union for all the elements, we have total $O(V^2)$ time spent in union. Which gives amortized $O(V)$. Now the problem isn't clear whether it is expecting amortized time complexity or not. So I'm wondering if any better approach is possible. Note the algorithm is running for all nodes and all edges. Hence I think amortized makes sense.

Here is my analysis (line, complexity)

1-3 $V$

4-9 $\frac{V}{2} \cdot union = \frac{V}{2} \cdot \frac{V}{2} = V^2 = V$ (amortized)

10 $V \cdot findset = V$

12-21 $E \cdot findset = E$

Since $E >= V - 1$, we have overall time complexity of $O(E)$.

0   MST-REDUCE(G, orig, c T)
1   for each v in V[G]
2       mark[v] <- FALSE
3       MAKE-SET(v)
4   for each u in V[G]
5       if mark[u] = FALSE
6           choose v in Adj[u] such that c[u,v] is minimized.
7           UNION(u,v)
8           T <- T union { orig(u,v) }
9           mark[u] <- mark[v] <- TRUE
10  V[G'] <- { FIND-SET(v) : v in V[G] }
11  E[G'] <- { }
12  for each (x,y) in E[G]
13      u <- FIND-SET(x)
14      v <- FIND-SET(y)
15      if (u,v) doesn't belong E[G']
16          E[G'] <- E[G'] union {(u,v)}
17          orig'[u,v] <- orig[x,y]
18          c'[u,v] <- c[x,y]
19      else if c[x,y] < c'[u,v]
20          orig'[u,v] <- orig[x,y]
21          c'[u,v] <- c[x,y]

• Please copy the algorithm (with your modification) in the question text. As for your analysis, the math seems doubtful (do you always mean to write $O(.)$?). Futhermore, the exercise suggests you have to modify the algorithm, but I can't see you have. And you don't use that the graph is sparse at all. So by these simple indicators, I don't think your solution is correct. – Raphael Aug 31 '12 at 7:36
• Thanks! There are much better UNION-FIND structures than linked lists, but those would not be "simple", I guess. I only see you use $E \geq V-1$ which is only a lower bound. You would have to use an upper bound on $E$ in terms of $V$. – Raphael Aug 31 '12 at 8:39