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 𝑂⁡(3𝑘⁢𝑛2) time. See this paper.