18.2.1. A Simple Algorithm

The core of the Steiner tree problem is to choose the right subset \(V' \subseteq V\) of vertices to include in \(T\). Indeed, if the vertex set \(V'\) of an optimal Steiner tree \(T\) for \(K\) is given, then \(V' \supseteq K\) and every spanning tree of \(G[V']\) is a Steiner tree for \(K\). Since \(T\) is a Steiner tree of minimum weight, it is therefore a minimum spanning tree of \(G[V']\). This leads to a trivial \(O^*(2^n)\)-time algorithm for the Steiner tree problem: Enumerate all \(2^n\) subsets of \(V\). For each such subset \(V'\) that is a superset of \(K\) and such that \(G[V']\) is connected, compute a minimum spanning tree of \(G[V']\). Report the tree of minimum weight among all spanning trees computed in this fashion.

Next we show that we can compute a minimum Steiner tree in \(O^*\bigl(3^k\bigr)\) time, where \(k = |K|\) is the number of vertices that are required to be in the Steiner tree.