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?

• I can't answer that question without reading the literature on the problem. Have you tried reading the literature yourself? Can you summarize what you found? Oct 14, 2010 at 13:55
• Much of the literature is concerned with finding approximation algorithms, some of which are quite good. The majority of these operate through cycle contraction, with good results. I'm having trouble finding literature for pruning instead of approximation, which is why I'm wondering if the pruning problem is a generalization of a more common problem that I can read up on. Any tips as to what literature is related would be welcome.
– Nate
Oct 14, 2010 at 16:16
• What function is being approximated by the approximation algorithms and how does this differ from pruning ? Oct 14, 2010 at 17:33
• The approximations are approximating the minimal strongly connected subgraph. As I said, they often use cycle contraction to do so. Pruning via cycle contraction may result in a non-optimal subgraph (hence, approximation). I want to prune such that I can guarantee I have not pruned any edges that appear the MSCS.
– Nate
Oct 14, 2010 at 18:11

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 wi=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.

• Yes, obviously, it is NP hard to find all such edges. I'm not looking for all such edges, I'm looking for a set of edges that you can determine are prune-able in polynomial time. The Floyd-Warshall algorithm can be used to find one such set of edges, as described above. I was wondering if there are any other ways to identify a subset of the removable edges in polynomial time.
– Nate
Oct 16, 2010 at 20:38