A two way minimum spanning tree of a directed graph

Question

Given a directed graph with weighted edges, what algorithm can be used to give a sub-graph that has minimum weight, but allows movement from any vertex to any other vertex in the graph (under the assumption that paths between any two vertices always exist).

Does such an algorithm exist?

Answer 1

This looks to be NP-Hard: The minimum weight strongly connected spanning subgraph problem.

I believe Hamiltonian cycle problem can be reduced to it: Given a graph G(V,E), construct a digraph DG with weight 1 for edges which appear and weight 100 (|V|+1) for edges that don't. DG has a minimum weight strongly connected spanning subgraph of weight exactly |V| if and only if G has a hamiltonian cycle.

The paper here has an approximation algorithm: http://portal.acm.org/citation.cfm?id=844363

Answer 2

Even though they weren't right themselves, taking the time to follow Vitalii's Wikipedia links quickly uncovered this algorithm:

http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm

Answer 3

Split every node in the graph into two nodes. One node will accept all of the incoming edges to the original node, and the other will have all of the outgoing edges. Then, drop the direction on all of the edges, so the graph is undirected. Then you can run a standard MST algorithm on the graph (Prim's, Kruskal's) and you will ensure that every original node can be traveled to by every other original node.

Answer 4

This is a Directed Steiner Tree problem. As the Steiner Tree, it's NP-Hard.

You can find some aproximate algorithms here :

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.8774&rep=rep1&type=ps

Answer 5

Pick any node and return it.

Did you perhaps mean find the largest strongly-connected sub-graph (least number of nodes removed possible), or the minimum-weight spanning subgraph (no node removals allowed)?