Dreyfus-Wagner DP algorithm is used to solve the Steiner Tree problem, and is mentioned in a starred exercise of CP4 book which was my motivation for writing this blog. I have found little reading material, if you know a useful link please consider posting it.

Steiner Tree problem is the problem of given a connected undirected graph with non-negative edge weights and a subset of $$$k$$$ vertices (terminal vertices) find a tree (Steiner Tree) of minimum total weight that includes all the terminal vertices, but may also include additional vertices (called Steiner points).

Steiner Tree problem is NP-hard, which means that there is no polynomial time solution for the general case. Dreyfus-Wagner DP runs in $$$O(3^k*v + 2^k*v^2 + v*(v + e)*\log(v))$$$ which is better than complete search approach but also insufficient for large instances of the problem. In CP4 book, the algorithm is recommended for $$$v \le 50$$$ and $$$k \le 11$$$.

The state of DP is the pair $$$(X,v)$$$ where $$$X$$$ is a subset of the set of terminal vertices and $$$v$$$ is a some vertex in the Steiner Tree whose subtree contains all terminal vertices in $$$X$$$. Let $$$K$$$ be the set of terminal vertices, to compute answer to the problem we call DP at state $$$(K, root)$$$ for all possible roots of Steiner Tree and take the minimum. To speed up DP, we use bitmasks to represent $$$X$$$ in DP state.

When $$$|X| = 1$$$, solution is trivial. We will use this as base case of the DP. Let $$$X = {x}$$$, we have $$$dp(X,v) = dist(x,v)$$$.

Now suppose $$$|X| > 1$$$. Our goal is to find a vertex $$$u$$$ in the subtree of $$$v$$$ in Steiner Tree which we can use to divide set $$$X$$$ into two smaller subsets. Starting from $$$v$$$ we perform DFS in given graph until we reach a vertex in $$$X$$$ or a vertex of $$$degree > 2$$$. This is our vertex $$$u$$$. The path from $$$v$$$ to $$$u$$$ is equivalent to going down in subtree of $$$v$$$ in Steiner Tree.

Now let's define our desired subset of $$$X$$$, we call it $$$Y$$$.

If $$$u \in X$$$, then let $$$Y = {u}$$$. Otherwise we choose a connected subgraph when $$$u$$$ is removed and let $$$Y$$$ equal the set of terminal vertices in that subgraph. Which is equivalent to choosing a subtree of $$$u$$$ in the Steiner Tree. In both cases, the important thing is that $$$Y$$$ is a proper subset of $$$X$$$.

Now we can write our DP transition:

$$$dp(X,v) = \min ( dist(v,u) + \min ( dp(Y,u) + dp(X-Y,u) ) )$$$

Now let's analyze the complexity of this DP. For each state $$$(X,v)$$$, if we consider all proper subsets of mask $$$X$$$ we can get an upper bound for total number of DP transition calls. The sum of number of subsets of all masks of size $$$k$$$ is $$$O(3^k)$$$. Thus, DP transition is calculated at most $$$O(3^k*v)$$$ times. We have a total of $$$O(2^k*v^2)$$$ states, each visited exactly once. Distances need to be pre-calculated at every node of the graph with Dijkstra which takes $$$O(v*(v + e)*\log(v) )$$$ time.

Useful Reference: https://www.imsc.res.in/~vraman/exact/suchy.pdf

Thank you for reading !!