Homework 5 Optional Problems

Consider an undirected graph with nonnegative edge costs. You are given a set of vertices called terminals. A Steiner tree is a subset of edges that contains a path between each pair of terminals. For example, if , 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 , where is a constant (like 4) and poly is some polynomial function.

ANSWER: Dreyfus-Wagner’s algorithm can compute a Steiner tree in time. See this paper.