I am writing this document to explain the Steiner tree problem and the algorithms I use to solve it. The Steiner tree problem asks me to connect a specific subset of “important” points (called terminals) in a graph using the least total edge weight, and unlike a normal spanning tree, I am allowed to use extra intermediate points (called Steiner points) if that helps reduce the overall cost. I find this problem important because it appears constantly in real infrastructure planning: laying cable, designing circuits, or connecting cities where I do not need every single point connected, only a chosen set of them.
History and Background
The problem is named after the Swiss mathematician Jakob Steiner, though the original geometric version (connecting three points with minimum total distance using an extra point) actually traces back to Pierre de Fermat and was later studied by Evangelista Torricelli in the 1600s. The generalized graph version of the Steiner tree problem, which is the one I focus on in this document, was formalized in the mid-20th century as combinatorial optimization matured. It was proven NP-hard in the 1970s, which is part of why so much research has gone into approximation algorithms rather than exact solvers for large instances.
Problem Statement
I am given an undirected, weighted graph $G = (V, E, w)$ and a subset of vertices $R \subseteq V$ called terminals. I need to find a tree $T$ that is a subgraph of $G$, connects all vertices in $R$, and minimizes the total edge weight of $T$. The tree may include additional non-terminal vertices from $V \setminus R$ if doing so reduces the total cost. This is the key difference from a minimum spanning tree, where I must connect every vertex; here I only need to connect the terminals, optionally through helper nodes.
Core Concepts
- Terminal: a vertex that must be included in the resulting tree.
- Steiner point: a non-terminal vertex used to reduce total connection cost.
- Steiner tree: the resulting minimum-weight tree connecting all terminals, possibly via Steiner points.
- Metric closure: a complete graph over the terminals where the edge weight between any two terminals equals the shortest path distance between them in the original graph. I use this concept heavily in the approximation algorithm.
- NP-hardness: the property that no known algorithm can solve every instance of this problem in polynomial time, which pushes me toward approximation methods for large graphs.
How It Works
Since exact solving is expensive, the most practical widely used approach I rely on is the 2-approximation algorithm based on minimum spanning trees. Here is how I execute it:
- I compute the metric closure over the terminal set $R$: for every pair of terminals, I find the shortest path distance in $G$.
- I build a complete graph $H$ over $R$ using these shortest path distances as edge weights.
- I compute a minimum spanning tree $T_H$ of $H$.
- I expand each edge of $T_H$ back into the actual shortest path it represents in $G$.
- I take the union of all these paths, which may contain redundant edges or cycles.
- I remove any redundant edges (using a spanning tree extraction on this union) to get the final approximate Steiner tree.
Working Principle
The intuition behind this method is that connecting terminals through their pairwise shortest paths and then finding the cheapest way to link those “virtual” direct connections captures most of the savings that true Steiner points would offer, even though it does not always find the exact optimal set of Steiner points. The mathematical guarantee is that this approach never produces a tree more than twice the weight of the true optimal Steiner tree, which is why it is called a 2-approximation. More advanced approaches, like the Robins-Zelikovsky algorithm, refine this further by considering how grouping three or more terminals through a shared Steiner point can save more than pairwise connections alone, pushing the approximation ratio down closer to 1.55.
Mathematical Foundation
I define the cost of a candidate Steiner tree $T$ as:
$$ w(T) = \sum_{e \in T} w(e) $$
I want to find:
$$ T^* = \arg\min_{T \supseteq R,\ T \text{ is a tree in } G} w(T) $$
For the 2-approximation bound, if $T_{OPT}$ is the true optimal Steiner tree and $T_{MST}$ is the tree produced by my metric closure MST approach, the classical result guarantees:
$$ w(T_{MST}) \leq 2 \left(1 – \frac{1}{|R|}\right) w(T_{OPT}) $$
which for large terminal sets approaches:
$$ w(T_{MST}) \leq 2 \cdot w(T_{OPT}) $$
Diagrams
flowchart TD
A[Given graph G and terminal set R] --> B[Compute shortest paths between all terminal pairs]
B --> C[Build complete metric closure graph H over R]
C --> D[Compute Minimum Spanning Tree of H]
D --> E[Expand each MST edge into its actual shortest path in G]
E --> F[Remove redundant edges/cycles to get final Steiner Tree]
Pseudocode
function STEINER_TREE_APPROX(G, R):
H = empty complete graph on vertex set R
for each pair (u, v) in R x R, u != v:
H.weight(u, v) = SHORTEST_PATH(G, u, v)
T_H = MINIMUM_SPANNING_TREE(H)
union_graph = empty graph
for each edge (u, v) in T_H:
path = SHORTEST_PATH_EDGES(G, u, v)
add path edges to union_graph
T = MINIMUM_SPANNING_TREE(union_graph) // removes redundant cycles
return T
Step-by-Step Example
Consider a graph with vertices {A, B, C, D, E}, terminals R = {A, C, E}, and edges: A-B (2), B-C (2), C-D (1), D-E (2), A-E (10), B-D (3).
- Shortest path A to C: A-B-C = 4.
- Shortest path C to E: C-D-E = 3.
- Shortest path A to E: comparing A-E (10) vs A-B-C-D-E (7), I pick 7.
- Metric closure graph H has edges: A-C (4), C-E (3), A-E (7).
- MST of H: I pick A-C (4) and C-E (3), skipping A-E (7) since it would create a cycle at higher cost. Total = 7.
- Expanding back: A-C becomes A-B-C, and C-E becomes C-D-E.
- Union of these paths: A-B, B-C, C-D, D-E. No redundant cycles exist, so this is my final Steiner tree with total weight 2+2+1+2 = 7.
In this case, B and D serve as Steiner points, and the terminals A, C, E are all connected at a total cost of 7, which happens to also be optimal here.
Time Complexity
Computing all-pairs shortest paths for the terminal set, if I use Dijkstra’s algorithm from each terminal, costs $O(|R| \cdot (E + V \log V))$ using a Fibonacci heap implementation. Building the metric closure MST with Prim’s or Kruskal’s algorithm costs $O(|R|^2 \log |R|)$. Expanding paths back and computing the final spanning tree on the union graph costs roughly $O(E \log V)$ again. So overall, the dominant cost is typically $O(|R| \cdot E \log V)$ for sparse to moderately dense graphs.
Space Complexity
I need $O(V + E)$ space to store the original graph, $O(|R|^2)$ space for the metric closure complete graph, and $O(V + E)$ additional space for the union graph built from expanded shortest paths. So overall space usage is $O(V + E + |R|^2)$.
Correctness Analysis
The 2-approximation guarantee follows from a classical argument: I take the optimal Steiner tree $T_{OPT}$ and perform a depth-first traversal around it, which produces a walk visiting every terminal and using each edge of $T_{OPT}$ at most twice, giving total walk weight $2 \cdot w(T_{OPT})$. From this walk I can extract a Hamiltonian-like path over the terminals whose cost, using shortest-path distances, is at most the walk’s weight, so the terminals’ minimum spanning tree in the metric closure cannot cost more than $2 \cdot w(T_{OPT})$ either, since an MST is always cheaper than or equal to any Hamiltonian path over the same vertices. This chain of inequalities is what proves my algorithm never produces a result worse than twice the true optimum.
Advantages
- The MST-based 2-approximation is simple to implement using algorithms I already know (Dijkstra, Prim/Kruskal).
- It runs efficiently even on graphs with thousands of vertices.
- It gives a provable worst-case bound, so I always know how far from optimal I could be.
- It naturally reduces to an exact minimum spanning tree solution when all vertices are terminals.
Disadvantages
- It does not guarantee the exact optimal answer, only a bounded approximation.
- Exact solvers (integer programming, dynamic programming over subsets) become extremely slow as the number of terminals grows, because the exact problem is NP-hard.
- Real-world instances with geometric constraints (Euclidean Steiner tree) require different specialized algorithms.
- Choosing good Steiner points in dense graphs can still be computationally expensive despite the approximation.
Applications
I most often see this algorithm applied in VLSI circuit design, where I need to connect specific pins on a chip with minimum wire length. It is also used in telecommunications and utility network design, where I connect a subset of cities or buildings to a shared backbone at minimum infrastructure cost, in phylogenetics for reconstructing evolutionary trees, and in multicast routing in computer networks where only a subset of nodes need to receive a data stream.
Implementation in C
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define MAXN 20
#define INF INT_MAX
int n; /* number of vertices in graph */
int graph[MAXN][MAXN]; /* adjacency matrix, INF if no direct edge */
int dist[MAXN][MAXN]; /* all-pairs shortest path results */
/* Floyd-Warshall to get all-pairs shortest paths, used to build
the metric closure over the terminal set. */
void compute_all_pairs_shortest_paths() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dist[i][j] = graph[i][j];
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] != INF && dist[k][j] != INF &&
dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
/* Prim's algorithm restricted to the terminal set, using metric
closure distances, to approximate the Steiner tree cost. */
int steiner_tree_cost_approx(int terminals[], int t_count) {
int in_tree[MAXN] = {0};
int min_dist[MAXN];
for (int i = 0; i < t_count; i++) min_dist[i] = INF;
min_dist[0] = 0;
int total = 0;
for (int count = 0; count < t_count; count++) {
int u = -1, best = INF;
for (int i = 0; i < t_count; i++)
if (!in_tree[i] && min_dist[i] < best) { best = min_dist[i]; u = i; }
in_tree[u] = 1;
total += min_dist[u];
for (int v = 0; v < t_count; v++) {
if (!in_tree[v]) {
int d = dist[terminals[u]][terminals[v]];
if (d < min_dist[v]) min_dist[v] = d;
}
}
}
return total;
}
int main() {
n = 5; /* A=0, B=1, C=2, D=3, E=4 */
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
graph[i][j] = (i == j) ? 0 : INF;
graph[0][1] = graph[1][0] = 2; /* A-B */
graph[1][2] = graph[2][1] = 2; /* B-C */
graph[2][3] = graph[3][2] = 1; /* C-D */
graph[3][4] = graph[4][3] = 2; /* D-E */
graph[0][4] = graph[4][0] = 10; /* A-E */
graph[1][3] = graph[3][1] = 3; /* B-D */
compute_all_pairs_shortest_paths();
int terminals[] = {0, 2, 4}; /* A, C, E */
int cost = steiner_tree_cost_approx(terminals, 3);
printf("Approximate Steiner tree cost over terminals: %d\n", cost);
return 0;
}
Sample Input and Output
Using the same graph and terminal set {A, C, E} from my worked example, running this program gives:
Approximate Steiner tree cost over terminals: 7
This matches the manual calculation I did earlier, confirming that B and D correctly serve as implicit Steiner points in the shortest paths used.
Optimization Techniques
I can speed up shortest path computation by using Dijkstra’s algorithm from each terminal instead of full Floyd-Warshall when the graph is large and sparse, since Floyd-Warshall’s $O(V^3)$ cost becomes impractical beyond a few hundred vertices. I can also apply the Robins-Zelikovsky loss-contracting technique, which considers “full components” connecting three or more terminals through a shared Steiner point, improving the approximation ratio at the cost of more computation. For very large instances, I sometimes use heuristic local search or simulated annealing to refine an initial MST-based solution.
Common Mistakes
I have seen implementations forget to remove redundant edges after expanding shortest paths back into the union graph, which leaves cycles and inflates the total cost unnecessarily. Another common mistake is treating this as a plain minimum spanning tree problem and forgetting that non-terminal vertices are optional, which leads to including unnecessary vertices and edges. I also notice people confuse the Euclidean Steiner tree problem (points in continuous space) with the graph Steiner tree problem (fixed graph structure), and these require genuinely different algorithms.
Further Reading
- Hwang, F.K., Richards, D.S., Winter, P., “The Steiner Tree Problem,” Annals of Discrete Mathematics, North-Holland, 1992.
- Karp, R.M., “Reducibility Among Combinatorial Problems,” 1972 (establishes NP-hardness context).
- Robins, G., Zelikovsky, A., “Improved Steiner Tree Approximation in Graphs,” SODA 2000. https://dl.acm.org/doi/10.5555/338219.338637
- Kou, L., Markowsky, G., Berman, L., “A fast algorithm for Steiner trees,” Acta Informatica, 1981.
- Wikipedia overview: https://en.wikipedia.org/wiki/Steiner_tree_problem
- Vazirani, V., “Approximation Algorithms,” Springer, 2001. https://link.springer.com/book/10.1007/978-3-662-04565-7
