# Computational Complexity - Research Seminar

## Xinhui Wang (University of Twente): *Exact Algorithms for the Steiner Tree Problem*

Sept. 5, 2008, 10:15 a.m.

E 1 3, Room 415

In this talk, the exact algorithms for the Steiner tree problem will be investigated. The Dreyfus-Wagner algorithm is a well-known dynamic programming method for computing minimum Steiner trees in general weighted graphs in time *O*(3^{k}), where *k* is the number of the terminals.

Firstly, two exact algorithms for the Steiner tree problem will be presented. The first one improves the running time of algorithm to *O*^{*}(2.684^{k}) by showing that the optimum Steiner tree *T* can be partitioned into *T* = *T*_{1} ∪ *T*_{2} ∪ *T*_{3} in a certain way such that each *T*_{i} is a minimum Steiner tree in a suitable contracted graph *G*_{i} with less than *k*/2 terminals. The second algorithm is in time *O*((2 + δ)^{k}) for any δ > 0.

Every rectilinear Steiner tree problem admits an optimal tree *T*^{*} which is composed of tree stars. Moreover, the currently fastest algorithm for the rectilinear Steiner tree

problem proceeds by composing an optimum tree *T*^{*} from tree star components in the cheapest way. Fößmeier and Kaufmann showed that any problem instance with *k* terminals has a number of tree stars in between 1.32^{k} and 1.38^{k}. We also present additional conditions on tree stars which allow us to further reduce the number of candidate components building the optimum Steiner tree to *O*(1.337^{k}).