Speeding up the Dreyfus–Wagner algorithm for minimum Steiner trees

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 terminal nodes to be connected. We improve its running time to $O^*(2.684^k)$ by showing that the optimum Steiner tree $T$ can be partitioned into $T = T_1 \cup T_2 \cup 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\over 2}$ terminals. In the rectilinear case, there exists a variant of the dynamic programming method that runs in $O^*(2.386^k)$. In this case, our splitting technique yields an improvement to $O^*(2.335^k)$