<p>As has been explained repeatedly above, finding the minimum-weight strongly-connected spanning subgraph ("SCSS") of a given weighted digraph is NP-complete, even in the special case when all weights are one and even when you only want to distinguish the case that there is a subgraph of weight n from the case that the optimal weight is larger than n.</p>

<p>However, to follow up on a comment of Warren Schudy: there is a simple polynomial-time approximation algorithm that gets an approximation ratio of 2: choose an arbitrary vertex s, find the minimum-weight arborescence out of s (subgraph that includes a path from s to all other vertices), find the minimum-weight arborescence into s, and take the union of the two arborescences. I believe this idea is due to Frederickson and JáJá, "Approximation algorithms for several graph augmentation problems", SIAM J. Comput. 1981.</p>

<p>Better approximations are known for the unweighted problem e.g. 1.64 by <a href="http://arxiv.org/abs/cs.DS/0205040" rel="nofollow">Khuller, Raghavachari, and Young, SIAM J. Comput. 1995</a>. I don't know of improvements for the weighted version but that may merely indicate that I didn't search hard enough.</p>

CC BY-SA 2.5
2010-12-28T06:31:05.947Z
2010-12-28T12:36:06.037Z
2010-12-28T12:36:06.037Z
David Eppstein
<p>If I understand your question correctly you aren't looking for a tree, or an arborescence, but rather a minimum weight set of arcs that suffice to keep the graph strongly connected.</p>

<p>Your problem is NP-complete by reduction from Hamiltonian cycle problem. Given an input undirected graph that you wish to find the Hamiltonian cycle of create a directed graph by replacing each edge with a pair of oppositely directed arcs. Give all arcs weight 1. This directed graph has a set of arcs that leave the graph strongly connected with weight at most the number of vertices if and only if it has a Hamiltonian cycle.</p>

<p>You can get a two-approximation by picking an arbitrary root, finding the minimum weight spanning tree with arcs pointing towards the root, finding the minimum weight spanning tree with arcs pointing away from the root, and then unioning the two sets of arcs.</p>

<p>I don't recognize this problem off the top of my head but have you tried looking in the various NP-complete problem directories for it?</p>

CC BY-SA 2.5
2010-10-12T13:41:16.607Z
In this problem, you're allowed to visit a vertex as many times as you want. Correct me if I'm wrong, but the Hamiltonian cycle requires you visit each vertex only once. Remove that stipulation, and it's no longer NP-complete, correct?
Nate
CC BY-SA 2.5
2010-10-12T13:42:33.640Z
This is surprising. Finding an MST would be much more efficient (effectively linear).
Dave Clarke
CC BY-SA 2.5
2010-10-12T14:46:13.833Z
Hamiltonian cycle does require you to visit each vertex exactly once. An equivalent formulation of Hamiltonian cycle is a cycle which visits each of the $n$ vertices at least once and uses at most $n$ edges. This equivalent formulation is helpful for understanding my reduction.
Warren Schudy
CC BY-SA 2.5
2010-10-12T15:09:38.427Z
Yes, but I don't wish to find a Hamiltonian cycle of the underlying directed graph. I'm allowed to visit each vertex more than once. Doesn't that break your reduction? If not, why not?
Nate
CC BY-SA 2.5
2010-10-12T15:30:26.567Z
Nate: I think you're missing the point. Warren's using Ham cycle for the reduction TO your problem to show NP-hardness. He's not trying to give you an algorithm.
Suresh Venkat
CC BY-SA 2.5
2010-10-12T15:49:49.063Z
You misunderstand me. I'm questioning the reduction. My problem allows revisiting vertexes, which means it isn't simply a digraph ham cycle. Warren assumes that to find my cycle I must find the Ham cycle of the underlying undirected graph. This is not the case. The reduction does not hold.
Nate
CC BY-SA 2.5
2010-10-12T15:57:48.957Z
@Nate: Warren already explained in his answer (and his comment) that an undirected graph G with n vertices has a Hamiltonian circuit if and only if the directed graph obtained from G by replicating each edge in both directions has a strongly connected spanning subgraph with at most n edges.  This claim establishes the correctness of the reduction.  If you reread his explanations and still not convinced, I guess you can ask for a clarification, but to me it seems that you have not understood what he is saying.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-12T18:07:46.133Z
As you say a spanning subgraph may or may not be a Hamiltonian cycle. However a spanning subgraph _of length $n$_ must necessarily be a Hamiltonian cycle. Therefore there is a spanning subgraph of length $n$ if and only if there is a Hamiltonian cycle. If this still doesn't make sense I'm not sure what else to say other than suggesting that you look in some textbook for example NP-hardness proofs, try to write a similar proof for this problem, and if that fails discuss this problem with a theory-minded person face to face.
Warren Schudy
CC BY-SA 2.5
2010-10-12T22:17:43.793Z
The minimal subgraph is not guaranteed to be length $n$, and each vertex can be revisited. We do not know the length of the minimal subgraph, and constructing a graph where the minimal subgraph is greater than $n$ is trivial. My issue isn't that what you're saying doesn't make sense, my issue is that you're giving me solutions to the wrong problem.
Nate
CC BY-SA 2.5
2010-10-12T22:55:53.540Z
Perhaps it would help if you read the literature on the minimum strongly connected spanning subgraph problem (start with a Google search). A quick glance at that literature suggests that that problem is NP-complete and that it is the same as your problem. Please either tell us how your problem differs from the minimum strongly connected spanning subgraph problem, or else locate an NP-completeness proof in the literature, point us to it, and let us know which specific step of the proof you don't understand.
Warren Schudy
CC BY-SA 2.5
2010-10-12T13:37:06.240Z
2010-10-12T13:37:06.240Z
Warren Schudy
<p>I've found a problem that boils down to this: I need to find the non-rooted MST of a directed weighted graph. In other words, I need to find the minimal set of edges such that from any one node in the graph you can get to all others.</p>

<p>This is similar to the rooted MST digraph problem, which the <a href="http://www.ce.rit.edu/~sjyeec/dmst.html" rel="nofollow">chu-liu</a> algorithm solves quite nicely. My intuition is to calculate the rooted MST for all nodes using chu-liu and then merge each, removing redundancies along the way. However, I don't believe that that would be optimal.</p>

<p>Has anybody been working on this? Can you point me towards some papers that I should read?</p>

<p>Thanks.</p>

CC BY-SA 2.5
2010-10-12T13:25:53.937Z
MST means minimal spanning tree, right? What does it mean to have a non-rooted tree?
Dave Clarke
CC BY-SA 2.5
2010-10-12T13:28:54.383Z
I guess "Minimal Spanning Tree" isn't the best term for what I'm looking for - "Minimal Spanning Subgraph", perhaps. Basically, a subset of the edges such that from any node you can get to any other node. Which is the same thing as an MST in an undirected graph, but not in a digraph.
Nate
CC BY-SA 2.5
2010-10-12T13:32:54.173Z
Minimal spanning subgraph would do the trick. Except that I can remove some edges from it to get an MST, which would be 'more' minimal.
Dave Clarke
CC BY-SA 2.5
2010-10-12T14:58:37.393Z
I would call it the “minimum strongly connected spanning subgraph,” and finding it is NP-complete as Warren Schudy explained in his answer.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-12T18:20:34.067Z
Do a google search of the phrase "minimum strongly connected spanning subgraph" that Tsuyoshi suggested and read the literature you find. There seems to be a fair amount of prior work on this problem.
Warren Schudy
<cc.complexity-theory><graph-theory><np-hardness>
Non-rooted MST of directed graph
Nate
# Non-rooted MST of directed graph

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

I've found a problem that boils down to this: I need to find the non-rooted MST of a directed weighted graph. In other words, I need to find the minimal set of edges such that from any one node in the graph you can get to all others.

This is similar to the rooted MST digraph problem, which the [chu-liu](http://www.ce.rit.edu/~sjyeec/dmst.html) algorithm solves quite nicely. My intuition is to calculate the rooted MST for all nodes using chu-liu and then merge each, removing redundancies along the way. However, I don't believe that that would be optimal.

Has anybody been working on this? Can you point me towards some papers that I should read?

Thanks.

**Tags:** cc.complexity-theory, graph-theory, np-hardness

> **Comments:**
> **username_1**: MST means minimal spanning tree, right? What does it mean to have a non-rooted tree?  
> **username_0**: I guess "Minimal Spanning Tree" isn't the best term for what I'm looking for - "Minimal Spanning Subgraph", perhaps. Basically, a subset of the edges such that from any node you can get to any other node. Which is the same thing as an MST in an undirected graph, but not in a digraph.  
> **username_1**: Minimal spanning subgraph would do the trick. Except that I can remove some edges from it to get an MST, which would be 'more' minimal.  
> **username_2**: I would call it the “minimum strongly connected spanning subgraph,” and finding it is NP-complete as username_3 explained in his answer.  
> **username_3**: Do a google search of the phrase "minimum strongly connected spanning subgraph" that Tsuyoshi suggested and read the literature you find. There seems to be a fair amount of prior work on this problem.  

---

## 2 answers

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

If I understand your question correctly you aren't looking for a tree, or an arborescence, but rather a minimum weight set of arcs that suffice to keep the graph strongly connected.

Your problem is NP-complete by reduction from Hamiltonian cycle problem. Given an input undirected graph that you wish to find the Hamiltonian cycle of create a directed graph by replacing each edge with a pair of oppositely directed arcs. Give all arcs weight 1. This directed graph has a set of arcs that leave the graph strongly connected with weight at most the number of vertices if and only if it has a Hamiltonian cycle.

You can get a two-approximation by picking an arbitrary root, finding the minimum weight spanning tree with arcs pointing towards the root, finding the minimum weight spanning tree with arcs pointing away from the root, and then unioning the two sets of arcs.

I don't recognize this problem off the top of my head but have you tried looking in the various NP-complete problem directories for it?

> **Comments:**
> **username_0**: In this problem, you're allowed to visit a vertex as many times as you want. Correct me if I'm wrong, but the Hamiltonian cycle requires you visit each vertex only once. Remove that stipulation, and it's no longer NP-complete, correct?  
> **username_1**: This is surprising. Finding an MST would be much more efficient (effectively linear).  
> **username_3**: Hamiltonian cycle does require you to visit each vertex exactly once. An equivalent formulation of Hamiltonian cycle is a cycle which visits each of the $n$ vertices at least once and uses at most $n$ edges. This equivalent formulation is helpful for understanding my reduction.  
> **username_0**: Yes, but I don't wish to find a Hamiltonian cycle of the underlying directed graph. I'm allowed to visit each vertex more than once. Doesn't that break your reduction? If not, why not?  
> **username_5**: username_0: I think you're missing the point. Warren's using Ham cycle for the reduction TO your problem to show NP-hardness. He's not trying to give you an algorithm.  
> **username_0**: You misunderstand me. I'm questioning the reduction. My problem allows revisiting vertexes, which means it isn't simply a digraph ham cycle. Warren assumes that to find my cycle I must find the Ham cycle of the underlying undirected graph. This is not the case. The reduction does not hold.  
> **username_2**: @username_0: Warren already explained in his answer (and his comment) that an undirected graph G with n vertices has a Hamiltonian circuit if and only if the directed graph obtained from G by replicating each edge in both directions has a strongly connected spanning subgraph with at most n edges.  This claim establishes the correctness of the reduction.  If you reread his explanations and still not convinced, I guess you can ask for a clarification, but to me it seems that you have not understood what he is saying.  
> **username_3**: As you say a spanning subgraph may or may not be a Hamiltonian cycle. However a spanning subgraph _of length $n$_ must necessarily be a Hamiltonian cycle. Therefore there is a spanning subgraph of length $n$ if and only if there is a Hamiltonian cycle. If this still doesn't make sense I'm not sure what else to say other than suggesting that you look in some textbook for example NP-hardness proofs, try to write a similar proof for this problem, and if that fails discuss this problem with a theory-minded person face to face.  
> **username_0**: The minimal subgraph is not guaranteed to be length $n$, and each vertex can be revisited. We do not know the length of the minimal subgraph, and constructing a graph where the minimal subgraph is greater than $n$ is trivial. My issue isn't that what you're saying doesn't make sense, my issue is that you're giving me solutions to the wrong problem.  
> **username_3**: Perhaps it would help if you read the literature on the minimum strongly connected spanning subgraph problem (start with a Google search). A quick glance at that literature suggests that that problem is NP-complete and that it is the same as your problem. Please either tell us how your problem differs from the minimum strongly connected spanning subgraph problem, or else locate an NP-completeness proof in the literature, point us to it, and let us know which specific step of the proof you don't understand.  

---

### Answer by username_4 on 2010-12-28. Score: 4

As has been explained repeatedly above, finding the minimum-weight strongly-connected spanning subgraph ("SCSS") of a given weighted digraph is NP-complete, even in the special case when all weights are one and even when you only want to distinguish the case that there is a subgraph of weight n from the case that the optimal weight is larger than n.

However, to follow up on a comment of username_3: there is a simple polynomial-time approximation algorithm that gets an approximation ratio of 2: choose an arbitrary vertex s, find the minimum-weight arborescence out of s (subgraph that includes a path from s to all other vertices), find the minimum-weight arborescence into s, and take the union of the two arborescences. I believe this idea is due to Frederickson and JáJá, "Approximation algorithms for several graph augmentation problems", SIAM J. Comput. 1981.

Better approximations are known for the unweighted problem e.g. 1.64 by [Khuller, Raghavachari, and Young, SIAM J. Comput. 1995](http://arxiv.org/abs/cs.DS/0205040). I don't know of improvements for the weighted version but that may merely indicate that I didn't search hard enough.


---

