Steiner tree problem

The steiner tree problem is a class of combinatorial optimization problems in which a minimum-length network must connect a specified set of points called terminals. The network may contain additional junctions, known as Steiner points or Steiner vertices, whose inclusion can reduce the total length. The problem has discrete formulations on weighted graphs and geometric formulations in continuous spaces, with the precise structural and computational properties depending on the underlying metric.

In the graph formulation, the input consists of a connected undirected graph (G=(V,E)), a nonnegative edge-weight function (w:E\to\mathbb{R}_{\geq 0}), and a terminal set (R\subseteq V). A feasible solution is a connected subgraph containing every vertex in (R). Its cost is the sum of the weights of its edges, and the objective is to minimize that cost:

[ \operatorname{OPT}(G,R)

\min\left{ \sum_{e\in E(T)}w(e): T\subseteq G,;R\subseteq V(T),;T\text{ is connected} \right}. ]

Because all edge weights are nonnegative, cycles can be removed without increasing the cost. An optimal solution can therefore be represented by a tree. Vertices of that tree outside (R) are the graph-theoretic Steiner vertices.

The problem differs from the minimum spanning tree problem because the latter requires all vertices of the input graph to be connected. If (R=V), the two problems coincide. When (R) is a proper subset of (V), an optimal Steiner tree may either omit nonterminal vertices or use selected nonterminals as junctions.

Geometric formulation

In the Euclidean Steiner tree problem, the terminals are points in the Euclidean plane and edge cost is ordinary Euclidean length. The solution may introduce junctions at arbitrary positions rather than selecting them from a finite input graph. A shortest connected network spanning the terminals is called a Steiner minimal tree.

Every Steiner point in a nondegenerate planar Euclidean solution has degree three, and its incident edges meet at angles of (120^\circ). A terminal may have a different degree because its position is fixed by the input. Edges in a minimal solution do not cross, since replacing a crossing by an appropriate local connection decreases or preserves total length.

The three-terminal case is the Fermat point problem. If every angle of the terminal triangle is smaller than (120^\circ), the three connecting segments meet at an interior point with (120^\circ) angles. If the triangle has an angle of at least (120^\circ), the optimal network joins the other two terminals directly to that vertex, and no additional Steiner point is required.

For (n) terminals in general position, a full Steiner topology has (n-2) Steiner points, each of degree three, and every terminal has degree one. Not every optimal tree has a full topology, because geometric degeneracies or sufficiently large terminal angles can suppress candidate junctions. The number of combinatorially possible topologies grows rapidly with (n), so exact geometric optimization requires both topology selection and continuous placement.

A related formulation uses the Manhattan distance. In the rectilinear Steiner tree problem, every edge is constrained to be horizontal or vertical. Although candidate junctions appear to range over a continuous plane, an optimal tree exists whose Steiner points lie on the intersections of horizontal and vertical lines through terminals. This finite set is called the Hanan grid.

Historical development

The geometric question originated in work on shortest networks connecting finitely many prescribed points. Pierre de Fermat posed the three-point problem during the seventeenth century, and Evangelista Torricelli supplied an early geometric construction. Jakob Steiner later examined related extremal constructions, and his name became attached to the general problem even though its principal forms developed across several distinct mathematical traditions.

During the twentieth century, the subject acquired a systematic distinction between the combinatorial topology of a candidate tree and the geometric coordinates of its junctions. Zdzisław Melzak developed a finite construction method for fixed Euclidean topologies in 1961. In 1976, You Watanabe formulated a candidate-topology encoding that represented planar Euclidean instances by terminal incidences and degree-three junction constraints. The encoding was used in exact enumeration methods that discarded incompatible topologies before solving the corresponding geometric subproblems.

The graph formulation emerged as part of the broader study of finite network optimization. It replaced arbitrary junction positions with vertices supplied by the input graph, thereby isolating the combinatorial choice of which edges and nonterminal vertices belong to the connecting tree.

Structural properties

A minimal graph Steiner tree contains no nonterminal leaf. Removing such a leaf and its incident edge would preserve connectivity among the terminals while weakly decreasing cost. After suppressing zero-cost degeneracies, every nonterminal vertex in a reduced solution has degree at least three. Degree-two nonterminals can be retained in the original graph representation, but they behave as internal points of a path rather than as branching junctions.

Shortest-path distances permit a metric interpretation. Replacing the original graph by its metric closure assigns each pair of vertices the length of a shortest path between them. A tree selected in the closure can then be expanded into paths of the original graph. Shared portions of those paths may create cycles, but deleting redundant edges produces a feasible tree without increasing total weight.

The terminal metric also yields an elementary comparison with spanning trees. A minimum spanning tree on the complete graph of terminals, weighted by shortest-path distance, has cost at most twice the optimum Steiner cost. The argument doubles the edges of an optimal Steiner tree, takes an Eulerian traversal, and shortcuts repeated vertices under the triangle inequality. Expanding the resulting terminal edges back into the input graph gives a polynomial-time factor-two approximation.

The ratio between the weight of a minimum spanning tree on the terminals and the weight of a minimum Steiner tree is called the Steiner ratio. Its value depends on the metric space. In the Euclidean plane, the ratio is at most (2/\sqrt{3}), with equality attained by an equilateral triangle under the conventional orientation of the ratio.

Computational complexity

The decision version asks whether a Steiner tree of cost at most a specified bound exists. It belongs to NP for finitely encoded graph instances because a proposed edge set can be checked for terminal connectivity and total weight in polynomial time. Richard Karp included the graph problem among the classical NP-complete problems identified in 1972. Consequently, a polynomial-time exact algorithm for arbitrary graph instances would imply (\mathrm{P}=\mathrm{NP}).

Hardness does not depend solely on unrestricted edge weights. The problem remains NP-complete under several constrained graph families and can be converted to unweighted form by suitable subdivisions when the weights are bounded integers. The Euclidean version is NP-hard, while the rectilinear geometric version has a finite certificate structure based on the Hanan grid and is NP-complete in its standard decision formulation.

Several boundary cases are polynomially solvable. With two terminals, an optimum is a shortest path. When the number of terminals is fixed, dynamic programming gives polynomial dependence on the graph size, although the dependence on the number of terminals is exponential. The problem is therefore fixed-parameter tractable when parameterized by (|R|).

Exact algorithms

A direct exact method enumerates terminal subsets and records the minimum cost of partial trees rooted at each graph vertex. Stuart Dreyfus and Robert Wagner developed the classical dynamic-programming formulation in 1971. For each nonempty subset (S\subseteq R) and vertex (v\in V), the state records the minimum cost of a tree connecting (S\cup{v}). Transitions either combine two partial trees at (v) or move the root through shortest-path relaxation.

A standard implementation has a running time of the form

[ O!\left(3^{|R|}|V|+2^{|R|}|V|^2\right), ]

up to differences in the shortest-path subroutine and state organization. This is exponential in the number of terminals but polynomial in the overall graph size for each fixed terminal count. Later subset-convolution and algebraic methods modify the exponential base or improve the polynomial factors without removing the NP-hardness of the unrestricted problem.

Integer programming formulations associate variables with selected edges and impose connectivity through cut constraints. For every vertex set (S\subset V) that separates at least one terminal from another, a feasible solution must choose an edge crossing the cut:

[ \sum_{e\in\delta(S)}x_e\geq 1. ]

The formulation contains exponentially many inequalities, but violated cuts can be identified through minimum-cut computations during branch-and-cut optimization. Directed formulations instead choose a root terminal and require sufficient connectivity from that root to every other terminal.

Approximation

The metric graph problem admits approximation algorithms that improve on the factor-two terminal spanning-tree construction. Their central mechanism is to evaluate small full components, each of which connects a bounded subset of terminals through possible Steiner vertices, and then combine selected components into a global tree. Increasing the permitted component size yields more detailed local representations while enlarging the associated optimization problem.

The minimum spanning tree heuristic has approximation ratio (2), whereas refined component-based algorithms attain ratios below (1.4) for the metric formulation. The problem is APX-hard, so a polynomial-time approximation scheme does not exist for general metric instances unless (\mathrm{P}=\mathrm{NP}).

Geometric restrictions lead to different approximation behavior. The Euclidean and rectilinear planar problems admit polynomial-time approximation schemes. These schemes use geometric decompositions that restrict how a near-optimal network crosses region boundaries, allowing dynamic programming over a finite collection of boundary configurations.

Applications and modeling scope

The graph Steiner tree formalizes network construction when only a designated subset of locations requires mutual connectivity and intermediate locations may serve as branching sites. A direct interpretation appears in telecommunications design, where terminals represent required endpoints and graph edges represent available links with construction costs. The same formulation also occurs as a subproblem in circuit routing, although physical design constraints often lead to the rectilinear variant.

The basic objective counts the cost of the union of selected edges and does not model capacities, demands, or failure recovery. Adding such conditions produces related network-design problems with different feasible sets and complexity properties. Likewise, directed edges lead to the directed Steiner tree problem, in which paths must respect orientation and the approximation behavior is substantially different from that of the undirected metric case.