A two way minimum spanning tree of a directed graph

views:

367

answers:

+7 Q:

A two way minimum spanning tree of a directed graph

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?

+2 A:

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

MatW 2010-05-10 07:32:20

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.

mvid 2010-05-11 07:51:21

This is NP-Hard. -1.

Moron 2010-05-19 16:20:24

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

MatW 2010-05-19 20:27:52

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

Moron 2010-05-19 20:57:52

Thanks for the clarification.

MatW 2010-05-19 21:43:05

+1 A:

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.

gmoomau 2010-05-11 08:20:34

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.

mvid 2010-05-11 22:16:51

+1 A:

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

Moron 2010-05-19 14:57:31

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

BlueRaja - Danny Pflughoeft 2010-05-19 19:37:55

@BlueRaja: The title says 'spanning tree', so I presume the latter.

Moron 2010-05-19 19:46:28

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

BlueRaja - Danny Pflughoeft 2010-05-19 19:54:30

+1 A:

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

jwinandy 2010-08-31 14:05:14

ansaurus

tags:

views:

answers:

A two way minimum spanning tree of a directed graph

related questions