Homework 5 Optional Problems

Consider an undirected graph \(G = (V,E)\) with nonnegative edge costs. You are given a set \(T \subseteq V\) of \(k\) vertices called terminals. A Steiner tree is a subset \(F \subseteq E\) of edges that contains a path between each pair of terminals. For example, if \(T = V\), then the Steiner trees are the same as the connected subgraphs. It is a fact that the decision version of the Steiner tree problem is NP-complete. Give a dynamic programming algorithm for this problem (i.e., for computing a Steiner tree with the fewest number of edges) that has running time of the form \(O(c^k \cdot poly(n))\), where \(c\) is a constant (like 4) and poly is some polynomial function.

ANSWER: Dreyfus-Wagner’s algorithm can compute a Steiner tree in \(O(3^kn^2)\) time. See this paper.