2

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.

unglinh279
  • 675
  • 4
  • 24
UTL
  • 65
  • 7
  • 1
    What does "*the difference between the maximum and minimum edges is minimum*" mean? What is a maximum and/or minimum edge in a subgraph? I cannot find anything in the literature that use the terms like this. "Maximum/minimum path" yes, but not min/max edge. – RBarryYoung Jul 24 '21 at 15:43
  • 2
    @RBarryYoung: The edges are weighted, so any given subgraph has a minimum- and maximum-weight edge. Subtract the former from the latter to get the cost of this subgraph. – j_random_hacker Jul 25 '21 at 00:55
  • Why is my post still closed? Can anyone help me? – UTL Jul 25 '21 at 16:16
  • Why is this question sill closed? Can anyone tell me what add? – UTL Jul 27 '21 at 01:47
  • I don't understand, what do I have to do to reopen the question? It is clear, it has an example and even an accepted answer! – UTL Aug 01 '21 at 04:29

1 Answers1

2

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.

j_random_hacker
  • 50,331
  • 10
  • 105
  • 169