18.2.3. A Dynamic Programming Solution

To obtain a dynamic programming formulation of the Steiner tree problem, we need the right recurrence describing an optimal Steiner tree. A natural attempt would be to consider all non-empty subsets \(K' \subseteq K\) and use Steiner trees for smaller subsets to construct Steiner trees for larger subsets. Unfortunately, as Figure 18.3 shows, this does not work because a Steiner tree for \(K\) may not be composed of Steiner trees for subsets of \(K\).

Figure 18.3: Coming soon!

As we will see, the following slight modification works: Instead of constructing optimal Steiner trees for all subsets of \(K\), we construct optimal Steiner trees for all sets \(K' \cup \{v\}\) such that \(\emptyset \subset K' \subset K\) and \(v \in V \setminus K\). For any such pair \((K',v)\), let \(T(K',v)\) be the weight of a minimum Steiner tree for \(K' \cup \{v\}\). The usefulness of considering this set of subproblems for the Steiner tree problem is made clear by the following lemma.

Lemma 18.3: If \(K' = \{u\}\) for some vertex \(u \in K\), then

\[T(K',v) = \textrm{dist}_G(u,v).\]

If \(|K'| > 1\), then

\[T(K',v) = \min_{\substack{\emptyset \subset K'' \subset K'\\u \in V \setminus K}} (T(K'',u) + T(K' \setminus K'',u) + \textrm{dist}_G(u,v)).\]

Proof: If \(K' = \{u\}\), then \(T(K',v)\) is the weight of an optimal Steiner tree for \((G,\{u,v\})\). Since a shortest path from \(u\) to \(v\) is a Steiner tree for \((G,\{u,v\})\), we have \(T(K',v) \le \mathrm{dist}_G(u,v)\). Conversely, any Steiner tree for \((G,\{u,v\})\) includes a path from \(u\) to \(v\) and thus has weight at least \(\mathrm{dist}_G(u,v)\), that is, \(T(K',v) \ge \mathrm{dist}_G(u,v)\). Together, these two inequalities prove that \(T(K',v) = \mathrm{dist}_G(u,v)\).

Now consider the case when \(|K'| > 1\). First observe that

\[T(K',v) \le \min_{\substack{\emptyset \subset K'' \subset K'\\u \in V \setminus K}} (T(K'',u) + T(T' \setminus K'',u) + \mathrm{dist}_G(u,v)). \tag{18.1}\]

Indeed, consider an arbitrary subset \(\emptyset \subset K'' \subset K'\) and an arbitrary vertex \(u \in V \setminus K\) and let \(T_1\) be a minimum Steiner tree for \(K'' \cup \{u\}\), let \(T_2\) be a minimum Steiner tree for \((K' \setminus K'') \cup \{u\}\), and let \(P\) be a shortest path from \(u\) to \(v\). Then \(T_1 \cup T_2 \cup P\) is a connected graph of weight at most \(T(K'',u) + T(K' \setminus K'',u) + \mathrm{dist}_G(u,v)\) that contains all vertices in \(K' \cup \{v\}\). Any spanning tree of \(T_1 \cup T_2 \cup P\) is a Steiner tree for \(K' \cup \{v\}\) and has weight at most \(w(T_1 \cup T_2 \cup P) \le T(K'', u) + T(K' \setminus K'', u) + \mathrm{dist}_G(u,v)\). Thus, since this analysis holds for every pair \((K'',u)\) such that \(\emptyset \subset K'' \subset K'\) and \(u \in V \setminus K\), (18.1) holds.

Figure 18.4: Coming soon!

HERE

Conversely, let \(T\) be a minimum Steiner tree for \(K' \cup \{v\}\) (see Figure 18.4). Let \(T'\) be the subtree of \(T\) that is the union of all paths in \(T\) between vertices in \(K'\), let \(u\) be the vertex in \(T'\) closest to \(v\) in \(T\), and let \(P\) be the path from \(u\) to \(v\) in \(T\). Then \(T = T' \cup P\) and \(T'\) and \(P\) are edge-disjoint. Thus, \(T(K',v) = w(T) = w(P) + w(T')\). Since \(P\) is a path from \(u\) to \(v\), we have \(\mathrm{dist}_G(u,v) \le w(P)\).

Now let \(T_1', \ldots, T_r'\) be the connected components of \(T' - u\) and let \(K_i' = K' \cap V(T_i')\) for all \(1 \le i \le r\). If \(u \in K\), then \(v\) is closer to \(u\)'s unique neighbour \(x\) in \(G\) than to \(u\) because \(v \in V \setminus K\). Since \(u \in T'\) and \(|K'| > 1\), we have \(x \in T'\), a contradiction because \(u\) is the vertex in \(T'\) closest to \(v\). This shows that \(u \in V \setminus K\).

Since a vertex in \(V \setminus K\) belongs to \(T'\) only if it belongs to at least one path in \(T'\) between two vertices in \(K'\), \(u \in V \setminus K\) implies that \(r \ge 2\) and \(K_i' \ne \emptyset\) for all \(1 \le i \le r\).

Now let \(K'' = K_1'\). Then \(\emptyset \subset K'' \subset K'\), the subtree \(T''\) of \(T'\) that is the union of all paths between vertices in \(K'' \cup \{u\}\) is a Steiner tree for \(K'' \cup \{u\}\), the subtree \(T'''\) of \(T'\) that is the union of all paths between vertices in \((K' \setminus K'') \cup \{u\}\) is a Steiner tree for \((K' \setminus K'') \cup \{u\}\), and \(T''\) and \(T'''\) are edge-disjoint. Thus,

\begin{align} T(K'',u) + T(K' \setminus K'',u) &\le w(T'') + w(T''')\\ &= w(T')\\ \llap{\smash{\min_{\substack{\emptyset \subset K'' \subset K'\\u \in V \setminus K}}}} (T(K'',u) + T(K' \setminus K'',u) + \mathrm{dist}_G(u,v)) &\le w(T') + w(P)\\ &= w(T)\\ &= T(K',v).\tag{18.2} \end{align}

Together, (18.1) and (18.2) show that

\[T(K',v) = \min_{\substack{\emptyset \subset K'' \subset K'\\u \in V \setminus K}} (T(K'',u) + T(T' \setminus K'',u) + \mathrm{dist}_G(u,v)).\quad \text{▨}\]

The proof of the following lemma is analogous to the proof of Lemma 18.3 and is omitted.

Lemma 18.4: Let \(\mathrm{OPT}\) be the weight of an optimal Steiner tree of \((G,K)\), let \(u\) be an arbitrary vertex in \(K\), and let \(v\) be \(u\)'s only neighbour in \(G\). Then \(v \in V \setminus K\) and \(\mathrm{OPT} = T(K \setminus \{u\}, v) + w(u,v)\).

By Lemma 18.3, we can compute \(T(K',v)\) for all \(\emptyset \subset K' \subset K\) and \(v \in V \setminus K\) as follows: First, we consider all vertex pairs \((u,v)\) such that \(u \in K\) and \(v \in V \setminus K\) and compute \(T({u},v) = \mathrm{dist}_G(u,v)\). This takes \(k\) applications of Dijkstra's algorithm and thus takes \(O(k \cdot (n \lg n + m)) = O^*\bigl(3^k\bigr)\) time. Then we consider the remaining subsets \(K' \subset K\) with \(|K'| > 1\) in order of increasing size and compute \(T(K',v)\) for each such set \(K'\) and every vertex \(v \in V \setminus K\). Note that the recurrence for \(T(K',v)\) depends only on values \(T(K'',u)\), where \(K'' \subset K\), so these values \(T(K'',u)\) have already been computed at the time when we compute \(T(K',v)\).

The computation of \(T(K',v)\) takes the minimum of \(\bigl(2^{|K'|} - 2\bigr) \cdot (n - k)\) subterms. Thus, it takes \(O\bigl(2^{|K'|} \cdot n\bigr)\) time to compute \(T(K',v)\). Since there are \(\binom{k}{j} \cdot (n - k) \le \binom{k}{j} \cdot n\) pairs \((K',v)\) such that \(|K'| = j\), the cost of computing all values \(T(K',v)\) is thus

\[\sum_{j=2}^k \binom{k}{j} \cdot n \cdot O\bigl(2^j n\bigr) < O\bigl(n^2\bigr) \cdot \sum_{j=0}^k \binom{k}{j} 2^j1^{k-j} = O\bigl(n^2\bigr) \cdot (2+1)^k = O\bigl(3^k \cdot n^2\bigr).\]

Once we have computed all values \(T(K',v)\), Lemma 18.4 allows us to compute an optimal Steiner tree in constant time. Thus, we obtain the following result.

Theorem 18.5: An optimal solution for a Steiner tree instance \((G,K)\) with \(|K| = k\) can be computed in \(O^*\bigl(3^k\bigr)\) time.