Algorithm for finding approximate minimum tree that spans a given subset of vertices?

Question

Given a weighted graph and a subset of two vertices in the graph, finding a minimum tree that spans all (both) vertices in the given subset reduces to finding a shortest path between the two vertices in the subset, which can be efficiently computed using standard path finding algorithms such as A^*.

But what if we have more than two vertices in the subset? What if it contains n vertices? Is there an efficient algorithm for finding an approximate minimum tree that spans all those vertices?

I guess this problem is a generalization of both the problem of finding a shortest path between two vertices in a graph and the problem of finding a minimum spanning tree of a graph.

Edit: I realized that this problem is known as the Steiner tree problem, and is apparently NP-complete, so I changed my request for the algorithm to find a minimum such tree to finding an approximate minimum tree.

Answer 1

There is! In fact there are two :) First of all we need to talk about what you are actually asking for. The algorithm you are looking for is an algorithm that finds the minimum spanning tree for any (coherent) graph. MSTs (minimal spanning trees) are trees that give the least weighted coherent tree that connects all points in the graph, using the minimal weight sum of vertices needed. Here is an example :

If you are intrested I recommend you read the wikipedia article https://en.wikipedia.org/wiki/Minimum_spanning_tree

The properties of of MSTs are numerous and a hole topic on its own in graph theorem. I'm not going to go in any further detail, as I just wanted to give some context.

Two algorithms are often used to solve this problem :

1. Prims algorithm Prims algorithm was first discovered by Vojtech Jarnik as early as 1930 and later rediscovered by Prim in 1957 and again rediscoverd by my personal idol Edsger W. Dijkstra in 1959 the alogritmn is called the Prim or Jarnik-Prim or Jarnik-Prim-Dijkstra alogrithm depending on the source. It creates a MST using the following pseudo code

Given : a coherent graph G(V,E) with n vertices
Result : R an MST for the graph G
Algorithm :
set R equal to a graph with one vertex and an empty set of edges
while R has less then n-1 edges repeat : 
    1) choose an edge (u,v) in E with u in R and v not in R and the weight of (u,v) being the         minimal weight of al the edges who have a start point in T but not an endpoint
    2) Add (u,v) to the edges of R together with the vertices v

Here is a visualization :

2) Kuskal's algorithm : An other algorithm a little less known algorithms is Kruskal's algorithm. It achieves exactly the same thing as Prim's algorithm, but it invariant defers and the pseudo code is the following :

    Given : a coherent graph G(V,E) with n vertices
    Result : R an MST for the graph G
    Make R a graph with an empty set of vertices an edges
    while R has less then n-1 edges repeat :
        1) take (u,v) the least weighted edge that does not make a circle in R
        2) add (u,v) to R ass well as their vertices
        // while adding the vertices you shouldnt keep doubles ofcourse

Here is a visualization :

The difference with Prim's algorithm is that Kruskal's algorithm does not have a coherent graph at all times. This is also not specified in the invariant of Kruskal's algorithm. Here is a link to the proof of correctness of both algortihms :

1. Prim : https://home.uncg.edu/cmp/faculty/srtate/330.f16/primsproof.pdf
2. Kruskal : http://people.qc.cuny.edu/faculty/christopher.hanusa/courses/634sp12/Documents/KruskalProof.pdf

Hope this answers your question.

Answer 2

There is no need to look for an approximate algorithm. State-of-the-art software usually finds optimal solutions even for Steiner tree problems with hundreds of thousands of edges. See https://scipjack.zib.de/ for the fastest software (disclaimer: I am one of the developers)