Algorithm to find minimum spanning tree of chosen vertices

Question

One can use Prim's algorithm or Kruskal's algorithm to find the minimum spanning tree/graph of a collection of vertices/nodes and edges/links. What I want though, is an algorithm that finds the minimum spanning graph of this collection, but the resulting graph needs to include only arbitrarily chosen nodes, instead of all nodes. It's okay if the resulting graph includes more nodes than just those needed.

Does such an algorithm exist? Perhaps one could just use Prim's (or Kruskal's) algorithm after modifying the graph to include only the needed nodes? But, I'm not sure how to modify the graph to do so while maintaining its connectedness.

For example, say we have a diamond shaped starting graph (with costs of links in brackets):

    A
(2)/ \(1)
  B   C
(2)\ /(5)
    D

Now, we arbitrarily decide that only nodes A and D are needed. If we started at A, we'd still want it to take the left path, because ((2 + 2) < (1 + 5)).

Say we modify the graph slightly:

    A
(2)/ \(1) (2)
  B   C ------E
(2)\ /(5)
    D

If we decide that only nodes A, D, and E are needed, we realize that the path with the minimum cost is not necessarily the one with the fewest links. Taking A--B--D and A--C--E costs 7, but A--C--D and C--E costs 8.

hmakholm left over Monica · Accepted Answer · 2012-10-30 20:04:00Z

7

What you want to find is a discrete Steiner tree. When not all vertices in the graph are mandatory but the tree is allowed to split at the optional vertices, the problem is NP-hard.

Wikipedia says (linked above) of this problem: it is believed that arbitrarily good approximation ratios cannot in general be achieved in polynomial time. There is a polynomial-time algorithm that finds a factor 1.39 approximation of a minimum Steiner tree.

answered Oct 30, 2012 at 20:04

hmakholm left over Monica

23.4k3 gold badges55 silver badges75 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Tespa42 Over a year ago

Okay, I think that I get it. The optional nodes are the only possible steiner nodes that might be used to shorten the length of the graph. I still don't know how approximate a solution though.

Collectives™ on Stack Overflow

Algorithm to find minimum spanning tree of chosen vertices

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related