18.2.2. Simplifying the Input

The dynamic programming algorithm for the Steiner tree problem is easier to formulate if we can guarantee that every vertex \(v \in K\) is a leaf of every Steiner tree for \(K\). This is guaranteed if every vertex in \(K\) has degree \(1\). The following transformation ensures this.

Given an input \((G,K)\), we transform it into an equivalent input \((G',K')\) such that every vertex in \(K'\) has degree \(1\). \(G'\) is obtained from \(G\) by adding a vertex \(v'\) to \(G\) for every vertex \(v \in K\). The only neighbour of \(v'\) is \(v\). We define \(K' = \{v' \mid v \in K\}\). The edge \((v,v')\) has weight \(0\) for all \(v \in K\). This is illustrated in Figure 18.2.

Figure 18.2: Coming soon!

Lemma 18.2: If \(T\) is a solution of the Steiner tree problem for \((G,K)\), then \(T' = T \cup \{(v,v') \mid v \in K\}\) is a solution of the Steiner tree problem for \((G',K')\) of weight \(w(T') = w(T)\).

If \(T'\) is a solution of the Steiner tree problem for \((G',K')\), then \(T = T'[V]\) is a solution of the Steiner tree problem for \((G,K)\) of weight \(w(T) = w(T')\).

Proof: If \(T\) is a Steiner tree for \((G,K)\), then it is a tree that contains all vertices in \(K\). Thus, \(T' = T \cup \{(v,v') \mid v \in K\}\) is a tree. Since it contains all vertices in \(K'\) and all its edges are edges of \(G'\), it is a Steiner tree for \((G',K')\). \(T'\) contains all edges of \(T\) plus all edges in \(\{(v,v') \mid v \in K\}\). Since each of the latter edges has weight \(0\), we have \(w(T') = w(T)\).

If \(T'\) is a Steiner tree for \((G',K')\), then it is a tree that contains all vertices in \(K'\). Since the only neighbour of each vertex \(v' \in K'\) is its corresponding vertex \(v \in K\), \(T'\) also contains all vertices in \(K\). Since each vertex \(v' \in K'\) has degree \(1\), it is a leaf of \(T'\). Thus, the subgraph \(T'[V]\) of \(T'\) obtained by removing all vertices in \(K'\) is a tree. Since \(T'[V]\) contains all vertices in \(K\) and all its edges are edges of \(G\), it is a Steiner tree for \((G,K)\). \(T\) contains the same edges as \(T'\) except the edges \({(v,v') \mid v \in K}\). Since each of the latter edges has weight \(0\), we have \(w(T) = w(T')\). ▨

Lemma 18.2 establishes a weight-preserving bijection between Steiner trees of \((G,K)\) and Steiner trees of \((G',K')\). Thus, this bijection maps minimum Steiner trees of \((G,k)\) to minimum Steiner trees of \((G',k')\) and vice versa. Therefore, it is sufficient to compute a minimum Steiner tree of \((G',K')\). From here on, we can therefore assume that the input is a pair \((G,K)\) where every vertex \(v \in K\) has degree \(1\).