Given a Directed Weighted Graph which is Strongly Connected. I need to find a strongly connected sub-graph out of this graph such that the difference between the maximum and minimum weight edges is minimum.
To be more clearly, I need to get rid of edges in such a way that after removing them, the graph will still be strongly connected and the difference between the maximum and minimum weight edges is minimum.
Here is an example:
The first line is the number of N nodes and M edges of this graph. The next M lines represent the edges of this graph.
3 6
1 2 8
2 3 32
3 1 16
1 3 81
3 2 243
2 1 27
The chosen N-nodes sub-graph would contain the edges:
1 2 8
2 3 32
3 1 16
The difference between the maximum and minimum weight edges is: 32 - 8 = 24. Which is minimum among all choices.
I'm looking for an optimal solution. There are at most 3000 nodes and 5000 edges.
Given an algorithm that tests whether a given digraph G = (V, E) is strongly connected in O(f(|V|, |E|)) time, this problem can be solved in time O(|E|*f(|V|, |E|)) -- and better than that if testing for strong connectivity can be done more quickly after adding or removing a single edge to an already-tested digraph.
Sort edges in increasing order by weight, and number them in this order. Initially, add the first (lowest-weight) edge to the set E' of selected edges; for as long E' is not strongly connected, add the next edge to it. If this loop does not terminate then G is not strongly connected. Otherwise, when it stops, after adding, say, edge j, we have found a minimum-difference solution given that we include edge 1. Record this (1, j) solution as the incumbent.
Now remove edge 1 from E', so that edge 2 is the lowest-weight edge remaining in E'. Leave all other already-decided edges in place, and begin adding the next-lowest-weight edges again, starting at edge j+1, until an SCG forms. This can be repeated to compute the minimum-difference solution given that the lowest-weight edge included is edge i, for each i <= |V|. Keep the best overall.
Note that when solving for the starting point i+1, it isn't necessary to get rid of the edges decided for the previous starting point i: If edges i, i+1, ..., j-1 do not form an SCG, then edges i+1, i+2, ..., j-1 do not form an SCG either. Exploiting this means the overall outer loop runs just |E| times, instead of O(|E|^2) times.