Pruning a strongly connected digraph Given a strongly connected digraph G with weighted edges, I would like to identify edges that are provably not part of any minimal strongly connected subgraph (MSCS) of G.

One method for finding such edges is a modified Floyd-Warshall algorithm. Using the Floyd-Warshall algorithm, one can identify which edges are never the best option for going from vertex i to j. These nodes can't be part of a MSCS because it's better to replace them with two or more other edges.

The Floyd-Warshall pruning technique works quite well when edge weights vary significantly, but very poorly when edge weights are similar but large in magnitude.

Do you know any effective pruning methods for large, similar edge weights? Is this problem equivalent to a more common problem that I don't recognize? Has this sort of pruning been studied before in the literature?
We assume that edge weights are positive integers.  Given a directed graph G with edge weights, call an edge e redundant if e does not belong to any minimum-weight strongly-connected spanning subgraphs of G.

We claim that unless P=NP, there is no polynomial-time algorithm that always finds a redundant edge in a given directed graph with edge weights as long as there is one.  More precisely:

Theorem.  Given a directed graph G with edge weights, it is NP-hard to find a redundant edge in G or declare that G does not have a redundant edge.

Proof.  The key observation is that if G has a unique minimum-weight strongly-connected spanning subgraph, then you can compute that subgraph by removing the redundant edges one by one.  Therefore, it remains to show that the uniqueness does not make the minimum-weight strongly-connected spanning subgraph problem any easier, but this is proved by the next Lemma.  QED.

Lemma.  Given a directed graph G with edge weights, it is NP-hard to compute the weight of the minimum-weight strongly-connected spanning subgraph of G even under the promise that G has a unique minimum-weight strongly-connected spanning subgraph.

Proof.  As you know, the problem without the promise is NP-hard (even for the unit-weight case) by a reduction from the Hamiltonian circuit problem.  We reduce the problem without the promise to the problem with the promise.

Let G be a directed graph with edge weights.  Label the edges of G by e0, e1, …, em−1, where m is the number of edges in G.  Let wi be the given weight of the edge ei.  Let the new weight w′i=2mwi+2i.  Then it is easy to verify that G with the new weights has a unique minimum-weight strongly-connected spanning subgraph.  It is also easy to verify that the minimum weight W of a strongly-connected spanning subgraph in G with the original weights can be computed from the minimum weight W′ in G with the new weights as W=⌊W′/2m⌋.  QED.