Incombinatorial mathematics, theSteiner tree problem, orminimum Steiner tree problem, named afterJakob Steiner, is anumbrella term for a class of problems incombinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefinedobjective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is theSteiner tree problem in graphs. Given anundirected graph with non-negative edge weights and a subset of vertices, usually referred to asterminals, the Steiner tree problem in graphs requires atree of minimum weight that contains all terminals (but may include additional vertices) and minimizes the total weight of its edges. Further well-known variants are theEuclidean Steiner tree problem and therectilinear minimum Steiner tree problem.

The Steiner tree problem in graphs can be seen as a generalization of two other famous combinatorial optimization problems: the (non-negative)shortest path problem and theminimum spanning tree problem. If a Steiner tree problem in graphs contains exactly two terminals, it reduces to finding the shortest path. If, on the other hand, all vertices are terminals, the Steiner tree problem in graphs is equivalent to the minimum spanning tree. However, while both the non-negative shortest path and the minimum spanning tree problem are solvable inpolynomial time, no such solution is known for the Steiner tree problem. Itsdecision variant, asking whether a given input has a tree of weight less than some given threshold, isNP-complete, which implies that the optimization variant, asking for the minimum-weight tree in a given graph, isNP-hard. In fact, the decision variant was amongKarp's original 21 NP-complete problems. The Steiner tree problem in graphs has applications incircuit layout ornetwork design. However, practical applications usually require variations, giving rise to a multitude of Steiner tree problem variants.

Most versions of the Steiner tree problem are NP-hard, but some restricted cases can be solved in polynomial time. Despite the pessimisticworst-case complexity, several Steiner tree problem variants, including the Steiner tree problem in graphs and the rectilinear Steiner tree problem, can be solved efficiently in practice, even for large-scale real-world problems.^[1][2]

The original problem was stated in the form that has become known as theEuclidean Steiner tree problem orgeometric Steiner tree problem: GivenN points in theplane, the goal is to connect them by lines of minimum total length in such a way that any two points may be interconnected byline segments either directly or via otherpoints and line segments.

While the problem is named after Steiner, it has first been posed in 1811 byJoseph Diez Gergonne in the following form: "A number of cities are located at known locations on a plane; the problem is to link them together by a system of canals whose total length is as small as possible".^[3]

It may be shown that the connecting line segments do not intersect each other except at the endpoints and form a tree, hence the name of the problem.

The problem forN = 3 has long been considered, and quickly extended to the problem of finding astar network with a single hub connecting to all of theN given points, of minimum total length.However, although the full Steiner tree problem was formulated in a letter byGauss, its first serious treatment was in a 1934 paper written in Czech byVojtěch Jarník andMiloš Kössler [cs]. This paper was long overlooked, but it already contains "virtually all general properties of Steiner trees" later attributed to other researchers, including the generalization of the problem from the plane to higher dimensions.^[4]

For the Euclidean Steiner problem, points added to the graph (Steiner points) must have adegree of three, and the three edges incident to such a point must form three 120 degree angles (seeFermat point). It follows that the maximum number of Steiner points that a Steiner tree can have isN − 2, whereN is the initial number of given points. (all these properties were established already by Gergonne.)

ForN = 3 there are two possible cases: if the triangle formed by the given points has all angles which are less than 120 degrees, the solution is given by a Steiner point located at theFermat point; otherwise the solution is given by the two sides of the triangle which meet on the angle with 120 or more degrees.

For generalN, the Euclidean Steiner tree problem isNP-hard, and hence it is not known whether anoptimal solution can be found by using apolynomial-time algorithm. However, there is apolynomial-time approximation scheme (PTAS) for Euclidean Steiner trees, i.e., anear-optimal solution can be found in polynomial time.^[5] It is not known whether the Euclidean Steiner tree problem is NP-complete, since membership to the complexity class NP is not known.

The rectilinear Steiner tree problem is a variant of the geometric Steiner tree problem in the plane, in which theEuclidean distance is replaced with therectilinear distance. The problem arises in thephysical design ofelectronic design automation. InVLSI circuits,wire routing is carried out by wires that are often constrained by design rules to run only in vertical and horizontal directions, so the rectilinear Steiner tree problem can be used to model the routing of nets with more than two terminals.^[6]

Steiner trees have been extensively studied in the context ofweighted graphs. The prototype is, arguably, theSteiner tree problemin graphs. LetG = (V, E) be an undirected graph with non-negative edge weights c and letS ⊆ V be a subset of vertices, calledterminals. ASteiner tree is a tree inG that spansS. There are two versions of the problem: in theoptimization problem associated with Steiner trees, the task is to find a minimum-weight Steiner tree; in thedecision problem the edge weights are integers and the task is to determine whether a Steiner tree exists whose total weight does not exceed a predefinednatural numberk. The decision problem is one ofKarp's 21 NP-complete problems; hence the optimization problem isNP-hard. Steiner tree problems in graphs are applied to various problems in research and industry,^[7] including multicast routing^[8] and bioinformatics.^[9]

A special case of this problem is whenG is acomplete graph, each vertexv ∈ V corresponds to a point in ametric space, and the edge weightsw(e) for eache ∈ E correspond to distances in the space. Put otherwise, the edge weights satisfy thetriangle inequality. This variant is known as themetric Steiner tree problem. Given an instance of the (non-metric) Steiner tree problem, we can transform it in polynomial time into an equivalent instance of the metric Steiner tree problem; the transformation preserves the approximation factor.^[10]

While the Euclidean version admits a PTAS, it is known that the metric Steiner tree problem isAPX-complete, i.e., unlessP = NP, it is impossible to achieve approximation ratios that are arbitrarily close to 1 in polynomial time. There is a polynomial-time algorithm thatapproximates the minimum Steiner tree to within a factor of${\displaystyle \ln (4)+\epsilon \approx 1.386}$;^[11]however, approximating within a factor${\displaystyle 96/95\approx 1.0105}$ is NP-hard.^[12] For the restricted case of Steiner Tree problem with distances 1 and 2, a 1.25-approximation algorithm is known.^[13] Karpinski andAlexander Zelikovsky constructed PTAS for the dense instances of Steiner Tree problems.^[14]

In a special case of the graph problem, the Steiner tree problem forquasi-bipartite graphs,S is required to include at least one endpoint of every edge inG.

The Steiner tree problem has also been investigated in higher dimensions and on various surfaces. Algorithms to find the Steiner minimal tree have been found on the sphere, torus,projective plane, wide and narrow cones, and others.^[15]

Other generalizations of the Steiner tree problem are thek-edge-connected Steiner network problem and thek-vertex-connected Steiner network problem, where the goal is to find ak-edge-connected graph or ak-vertex-connected graph rather than any connected graph. A further well-studied^[16] generalization is thesurvivable network design problem (SNDP) where the task is to connect each vertex pair with a given number (possibly 0) of edge- or vertex-disjoint paths.

The Steiner problem has also been stated in the general setting of metric spaces and for possibly infinitely many points.^[17]

The general graph Steiner tree problem can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of the graph induced by the terminal vertices, as first published in 1981 by Kou et al.^[18] The metric closure of a graphG is the complete graph in which each edge is weighted by the shortest path distance between the nodes inG. This algorithm produces a tree whose weight is within a2 − 2/t factor of the weight of the optimal Steiner tree wheret is the number of leaves in the optimal Steiner tree; this can be proven by considering a traveling salesperson tour on the optimal Steiner tree. This approximate solution is computable in O(|S| |V|²)polynomial time by first solving theall-pairs shortest paths problem to compute the metric closure, then by solving theminimum spanning tree problem.

Another popular algorithm to approximate the Steiner tree in graphs was published by Takahashi and Matsuyama in 1980.^[19] Their solution incrementally builds up the Steiner tree by starting from an arbitrary vertex, and repeatedly adding the shortest path from the tree to the nearest vertex inS that has not yet been added. This algorithm also has O(|S| |V|²) running time, and produces a tree whose weight is within2 − 2/|S| of optimal.

In 1986, Wu et al.^[20] improved dramatically on the running time by avoiding precomputation of the all-pairs shortest paths. Instead, they take a similar approach toKruskal's algorithm for computing a minimum spanning tree, by starting from a forest of |S| disjoint trees, and "growing" them simultaneously using a breadth-first search resemblingDijkstra's algorithm but starting from multiple initial vertices. When the search encounters a vertex that does not belong to the current tree, the two trees are merged into one. This process is repeated until only one tree remains. By using aHeap (data structure) to implement the priority queue and adisjoint-set data structure to track to which tree each visited vertex belongs, this algorithm achieves O(|E| log |V|) running time, although it does not improve on the2 − 2/t cost ratio from Kou et al.

A series of papers provided approximation algorithms for the minimum Steiner tree problem with approximation ratios that improved upon the2 − 2/t ratio. This sequence culminated with Robins and Zelikovsky's algorithm in 2000 which improved the ratio to 1.55 by iteratively improving upon the minimum cost terminal spanning tree. More recently, however, Byrka et al. proved an${\displaystyle \ln (4)+\epsilon \le 1.39}$ approximation using a linear programming relaxation and a technique called iterative, randomized rounding.^[11]

The general graph Steiner tree problem is known to befixed-parameter tractable, with the number of terminals as a parameter, by the Dreyfus-Wagner algorithm.^[21][22] The running time of the Dreyfus-Wagner algorithm is${\displaystyle 3^{|S|}\text{poly}(n)}$, wheren is the number of vertices of the graph andS is the set of terminals. Faster algorithms exist, running in${\displaystyle c^{|S|}\text{poly}(n)}$ time for any${\displaystyle c>2}$ or, in the case of small weights,${\displaystyle 2^{|S|}\text{poly}(n)W}$ time, whereW is the maximum weight of any edge.^[23][24] A disadvantage of the aforementioned algorithms is that they useexponential space; there exist polynomial-space algorithms running in${\displaystyle 2^{|S|}\text{poly}(n)W}$ time and${\displaystyle (7.97{)}^{|S|}\text{poly}(n)\log W}$ time.^[25][26]

It is known that the general graph Steiner tree problem does not have a parameterized algorithm running in${\displaystyle 2^{ϵt}\text{poly}(n)}$ time for any, wheret is the number of edges of the optimal Steiner tree, unless theSet cover problem has an algorithm running in${\displaystyle 2^{ϵn}\text{poly}(m)}$ time for some, wheren andm are the number of elements and the number of sets, respectively, of the instance of the set cover problem.^[27] Furthermore, it is known that the problem does not admit apolynomial kernel unless${\displaystyle \mathsf{\text{coNP}}\subseteq \mathsf{\text{NP/poly}}}$, even parameterized by the number of edges of the optimal Steiner tree and if all edge weights are 1.^[28]

While the graph Steiner tree problem does not admit apolynomial kernel unless${\displaystyle \mathsf{\text{coNP}}\subseteq \mathsf{\text{NP/poly}}}$ parameterized by the number of terminals, it does admit apolynomial-sized approximate kernelization scheme (PSAKS): for any${\displaystyle \epsilon >0}$ it is possible to compute a polynomial-sized kernel, which looses only a${\displaystyle 1+\epsilon }$ factor in the solution quality.^[29]

When parameterizing the graph Steiner tree problem by the numberp of non-terminals (Steiner vertices) in the optimum solution, the problem isW[1]-hard (in contrast to the parameterization by the number of terminals, as mentioned above). At the same time the problem isAPX-complete and thus does not admit aPTAS, unlessP = NP. However, aparameterized approximation scheme exists, which for any${\displaystyle \epsilon >0}$ computes a${\displaystyle (1+\epsilon )}$-approximation in${\displaystyle 2^{O(p^2/{\epsilon }^4)}{n}^{O(1)}}$ time.^[30] Also a PSAKS exists for this parameterization.^[30]

TheSteiner ratio is thesupremum of the ratio of the total length of the minimum spanning tree to the minimum Steiner tree for a set of points in the Euclidean plane.^[31]

In the Euclidean Steiner tree problem, theGilbert–Pollak conjecture is that the Steiner ratio is${\displaystyle \frac{2}{\sqrt{3}}\approx 1.1547}$, the ratio that is achieved by three points in anequilateral triangle with a spanning tree that uses two sides of the triangle and a Steiner tree that connects the points through the centroid of the triangle. Despite earlier claims of a proof,^[32] the conjecture is still open.^[33] The best widely acceptedupper bound for the problem is 1.2134, byChung & Graham (1985).

For the rectilinear Steiner tree problem, the Steiner ratio is exactly${\displaystyle \frac{3}{2}}$, the ratio that is achieved by four points in a square with a spanning tree that uses three sides of the square and a Steiner tree that connects the points through the center of the square.^[34] More precisely, for${\displaystyle L_1}$ distance the square should be tilted at${\displaystyle {45}^{\circ }}$ with respect to the coordinate axes, while for${\displaystyle L_{\mathrm{\infty }}}$ distance the square should be axis-aligned.

• Opaque forest problem
• Travelling salesman problem

Wikimedia Commons has media related toSteiner tree problem.

• GeoSteiner (Software for solving Euclidean and rectilinear Steiner tree problems; source available, free for non-commercial use)
• SCIP-Jack (Software for solving the Steiner tree problem in graphs and 14 variants, e.g., prize-collecting Steiner tree problem; free for non-commercial use)
• Fortran subroutine for finding the Steiner vertex of a triangle (i.e.,Fermat point), its distances from the triangle vertices, and the relative vertex weights.
• Phylomurka (Solver for small-scale Steiner tree problems in graphs)
• https://www.youtube.com/watch?v=PI6rAOWu-Og (Movie: solving the Steiner tree problem with water and soap)
• Noormohammadpour, Mohammad; Raghavendra, Cauligi S.; Rao, Sriram; Kandula, Srikanth (2017), "Using Steiner Trees to Minimize Average Completion Times of Bulk Data Transfers",DCCast: Efficient Point to Multipoint Transfers Across Datacenters, USENIX Association,arXiv:1707.02096
• Hazewinkel, M. (2001) [1994],"Steiner tree problem",Encyclopedia of Mathematics,EMS Press
• M. Hauptmann, M. Karpinski (2013): A Compendium on Steiner Tree Problems

• NP-complete problems
• Trees (graph theory)
• Computational problems in graph theory
• Geometric algorithms
• Geometric graphs

• Articles with short description
• Short description is different from Wikidata
• Use dmy dates from May 2022
• CS1 Russian-language sources (ru)
• Commons category link is on Wikidata