Dreyfus-Wagner Algorithm

Purpose: Solve the Steiner tree problem exactly: given a graph and a set of $k$ terminals, find the minimum-weight connected subgraph containing all terminals. Runs in $O(3^{k}n+2^k{n}^2+n^3)$ — polynomial in $n$, exponential only in $k$.

Steiner tree

Unlike an MST, the tree may use extra “Steiner” vertices not among the terminals. With $k=2$ it is a shortest path; with $k=n$ it is an MST; in between it is NP-hard.

Algorithm

State: dp[mask][v] = minimum cost of a tree that connects the terminal set mask and contains vertex $v$.

Base: dp[{i}][t_i] = 0 for each terminal $t_i$; dp[{i}][v] = dist(t_i, v).

Two transitions:

1. Merge two sub-trees meeting at the same vertex:
   $\text{dp}[\text{mask}][v]={\min }_{\varnothing \ne \text{sub}⊊\text{mask}}(\text{dp}[\text{sub}][v]+\text{dp}[\text{mask}\setminus \text{sub}][v]).$
2. Grow by moving the meeting point along an edge — a shortest-path relaxation over the whole graph for each mask:
   $\text{dp}[\text{mask}][v]={\min }_u(\text{dp}[\text{mask}][u]+w(u,v)).$
   Implement this with a Dijkstra seeded from every vertex with its current dp[mask][·] value.

Answer: ${\min }_v\text{dp}[\text{full}][v]$.

Code

const long long INF = 1e18;
 
long long steiner(int n, const vector<vector<pair<int,long long>>>& adj,
                  const vector<int>& term) {
    int k = term.size(), FULL = 1 << k;
    vector<vector<long long>> dp(FULL, vector<long long>(n, INF));
    for (int i = 0; i < k; i++) dp[1 << i][term[i]] = 0;
 
    for (int mask = 1; mask < FULL; mask++) {
        // 1. merge sub-trees at the same vertex
        for (int v = 0; v < n; v++)
            for (int sub = (mask - 1) & mask; sub; sub = (sub - 1) & mask)
                if (dp[sub][v] < INF && dp[mask ^ sub][v] < INF)
                    dp[mask][v] = min(dp[mask][v], dp[sub][v] + dp[mask ^ sub][v]);
 
        // 2. Dijkstra to move the meeting point
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
        for (int v = 0; v < n; v++) if (dp[mask][v] < INF) pq.push({dp[mask][v], v});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dp[mask][u]) continue;
            for (auto [v, w] : adj[u])
                if (d + w < dp[mask][v]) { dp[mask][v] = d + w; pq.push({dp[mask][v], v}); }
        }
    }
    return *min_element(dp[FULL - 1].begin(), dp[FULL - 1].end());
}

Complexity

• Subset enumeration: ${\sum }_{\text{mask}}{2}^{|\text{mask}|}=3^k$, times $n$ vertices → $O(3^{k}n)$
• Dijkstra per mask: $O(2^k(m+n\log n))$
• Space: $O(2^{k}n)$

Practical up to $k\approx 12$-$15$ with $n$ in the thousands.

Correctness

Any optimal Steiner tree, rooted at any vertex $v$ it contains, either (a) has $v$ as a branching point, in which case it decomposes into two sub-trees each spanning a subset of the terminals — the merge transition; or (b) has $v$ as a degree-1 or pass-through vertex, in which case removing the edge at $v$ gives a smaller tree containing a neighbour — the grow transition. The DP considers both cases exhaustively. ∎

Variants / Use Cases

• Steiner tree in a grid / on a plane — the geometric version (Euclidean Steiner tree) is also NP-hard, with a different $\sqrt{3}/2$ structure
• 2-approximation — build the metric closure over terminals, take its MST, expand back to paths; ratio 2, polynomial. The best known ratio is $\ln 4+\epsilon \approx 1.386$.
• Steiner Tree — the topic page
• Held-Karp — the same “DP over subsets of a small special set” pattern
• Network design, VLSI routing, phylogenetics — where Steiner trees originate