10
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Warren Schudy Oct 14 '10 at 13:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Nate Oct 14 '10 at 16:16
  • 1
    $\begingroup$ What function is being approximated by the approximation algorithms and how does this differ from pruning ? $\endgroup$ – Suresh Venkat Oct 14 '10 at 17:33
  • $\begingroup$ 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. $\endgroup$ – Nate Oct 14 '10 at 18:11
3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Nate Oct 16 '10 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.