18.2. Steiner Tree

The Steiner tree problem is a generalization of the minimum spanning tree problem:

Steiner Tree Problem: Given a graph \(G = (V, E)\), a weight function \(w : E \rightarrow \mathbb{R}\), and a subset of vertices \(K \subseteq V\), compute a tree \(T \subseteq G\) of minimum weight \(w(T) = \sum_{e \in T}w_e\) and such that all vertices in \(K\) belong to \(T\).

Another way of describing the tree \(T\) we are looking for in the Steiner tree problem is that it is the cheapest subgraph of \(G\) that contains a path between every pair of vertices in \(K\): It connects the vertices in \(K\) together.

The minimum spanning tree problem is the Steiner tree problem with \(K = V\). The problem of finding a shortest path between two vertices \(s\) and \(t\) is the Steiner tree problem with \(K = \{s, t\}\). Both of these problems can be solved in polynomial time. For any choice of \(K\) between these two extremes of \(|K| = 2\) and \(|K| = n\), the Steiner tree problem is NP-hard.

What makes the Steiner tree problem hard is that the desired tree \(T\) is allowed but not required to include any of the vertices in \(V \setminus K\). Even if the subgraph \(G[K]\) of \(G\) is connected, it may be beneficial to include additional vertices in \(T\) if this allows us to connect the vertices in \(K\) more cheaply to each other than using only edges connecting the vertices in \(K\) directly. Figure 18.1 illustrates this:

Figure 18.1: Coming soon!

It is not hard to see that if we know the set of vertices \(V'\) included in \(T\), then \(T\) is simply a minimum spanning tree of the subgraph \(G[V']\) of \(G\) and can thus be computed in polynomial time. Finding \(V'\) is indeed the hard part. In the minimum spanning tree problem, we have \(K = V\), so there is no choice which vertices to include in \(T\). When computing a shortest path between two vertices, we don't know which vertices are part of this path but the fact that we have only two vertices in \(K\) makes finding the set \(V'\) of vertices to be included in \(T\) easy enough to solve in polynomial time.