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?

Pentastyle

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

Elba

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

Ivy

Edmond's algorithm only assures that every node in a graph will be accessible from the root, not that every node will be accessible from every other node. – Pentastyle

What has my link's NP classification got to do with it's relevance to the original question? – Ivy

By "this is NP-Hard", I mean the original question. Your algorithm is a polytime algorithm for a different problem. – Elba

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.

Dogy

Unfortunately this will not work, as it will add unnecessary edges to the final graph. At least one node will have an extra edge attached to it, even if it doesn't need to have that edge. For example, in a graph with vertices A, B, C and edges AB, BA, BC, CB, AC, CA, the minimal spanning of the graph may be just the edges AB, BC, CA. But using your method those 3 edges would not be attached to one another, and additional edges would need to be added to finish the MST. – Pentastyle

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

Annecorinne

But a directed Steiner Tree requires a root, doesnt it? – Women

The optimum root vertex may be found by the algorithms but you could specify a root along with the set of vertex. – Annecorinne

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)?

Aerology

The title says 'spanning tree', so I presume the latter. – Elba

@Moron: Ah, I missed that :) in which case, your answer is correct. – Aerology