Question

2. Let G = (V, E) be an undirected connected graph with n vertices and with an edge-weight function w : E → Z. An edge (u, v) ∈ E is sparkling if it is contained in some minimum spanning tree (MST) of G. The computational problem is to return the set of all sparkling edges in E. Describe an efficient algorithm for this computational problem. You do not need to use pseudocode. What is the asymptotic time complexity of your algorithm?

Answer 1

First of all, please understand that if every edge in graph G have distinct weights, then there will be unique minimum spanning tree and every edge in minimum spanning tree will be sparkling edge. Hence in such case there will be only n-1 sparkling edges.

The only case when there can be more than n-1 sparking edges is when there are multiple edges in a cycle and this edge is maximum weighted edge, then either one of edge can be part of minimum spanning tree and other edge can be discarded. Hence both edges will be sparking edge.

So what we will do here is that, we will compute minimum spanning tree first using either Prim's or Kruskal's algorithm. Hence the edges in this MST are definitely marked as sparkling edge. And then among the edges which are not part of MST T, lets call these set of edges as rejected set R.  

So from set R, we will select the edge one by one. Let us say we select edge e, we will see if there is any other edges in MST T which has same weight as R. If none of the edges in MST has same weight as w(e), then reject this edge since e cannot be sparkling edge.

If there is some other edge f in MST, with same weight as w(e), then remove edge f from MST and add edge e into MST. If after removing edge f and adding edge e still make the MST a connected spanning tree over n vertices then mark edge e as sparkling edge since e and f has same weight and are in same cycle and hence selecting either of them makes MST. If removing edge f and adding edge e does not make T as connected spanning tree over |V|=n vertices then 'e' will not be sparkling edge, so remove e and add back edge f into MST.

Do this process over all the rejected vertices and finally at the end we will get all the sparkling edges.

Below is the algorithm:-

SPARKLING_EDGE(G=(V,E))

1. For the given graph G=(V,E) compute MST T //Computing minimum spanning tree T from graph T

2. Sparkling_Edge = EMPTY; //This set will contain list of all sparkling edge at the end

3. For every edge e in T:-

4.........Sparkling_Edge.Add( e ); //Add every edge in T into list of Sparkling Edge

5. Let R = G - T //R contains those edges which are in G but not in MST T. Hence R contains rejected edge.

6. For every edge e in R:-

7............If MST T does not have any edge f with w(f) = w(e):-   

8.....................then continue //Since e cannot be sparkling edge, if there is no edge f in T with w(f) == w(e)

9..........else :-

10...................Remove edge f from T and add edge e

11...................If T is connected spanning tree over n vertices:- //Test if removing f and adding e, still connect all vertices

12............................then Sparkling_Edge.Add(e) //This means e and f have same weight in some common cycle

13...................else continue;

14. Return Sparkling_Edge

Time complexity :- Computing MST will take time O(E log E). Then for every edge e, testing them for same weight and checking whether removal of one edge and addition of other leads the tree T connected will take O(E(E+V)) time. Hence total time complexity will be O(E log E) + O(E(E+V)) = O(E² + EV).

Please comment for any clarification.