<p>We assume that edge weights are positive integers.  Given a directed graph <i>G</i> with edge weights, call an edge <i>e</i> <em>redundant</em> if <i>e</i> does not belong to any minimum-weight strongly-connected spanning subgraphs of <i>G</i>.</p>

<p>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:</p>

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

<p><strong>Proof</strong>.  The key observation is that if <i>G</i> has a <em>unique</em> 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.  <strong>QED</strong>.</p>

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

<p><strong>Proof</strong>.  As <a href="https://cstheory.stackexchange.com/questions/2129/non-rooted-mst-of-directed-graph">you know</a>, 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.</p>

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

CC BY-SA 2.5
2010-10-16T20:38:47.740Z
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
CC BY-SA 2.5
2010-10-15T00:59:51.227Z
2010-10-16T12:40:01.310Z
2017-04-13T12:32:28.077Z
Tsuyoshi Ito
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 2.5
2010-10-14T13:55:54.090Z
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?
Warren Schudy
CC BY-SA 2.5
2010-10-14T16:16:25.853Z
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
CC BY-SA 2.5
2010-10-14T17:33:12.767Z
What function is being approximated by the approximation algorithms and how does this differ from pruning ?
Suresh Venkat
CC BY-SA 2.5
2010-10-14T18:11:15.420Z
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
<ds.algorithms><graph-theory><graph-algorithms>
Pruning a strongly connected digraph
Nate
# Pruning a strongly connected digraph

(Asked by: username_0 on 2010-10-14)

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?

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: What function is being approximated by the approximation algorithms and how does this differ from pruning ?  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_3 on 2010-10-15. Score: 3 | Accepted answer

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](https://cstheory.stackexchange.com/questions/2129/non-rooted-mst-of-directed-graph), 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 *e*0, *e*1, …, *e**m*−1, where *m* is the number of edges in *G*. Let *w**i* be the given weight of the edge *e**i*. Let the new weight *w*′*i*=2*m**w**i*+2*i*. 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*′/2*m*⌋. **QED**.

> **Comments:**
> **username_0**: 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.  

---

