Steiner tree problem
If a Steiner tree problem in graphs contains exactly two terminals, it reduces to finding the shortest path.
The Steiner tree problem in graphs has applications in circuit layout or network 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.
[1][2] The original problem was stated in the form that has become known as the Euclidean Steiner tree problem or geometric Steiner tree problem: Given N points in the plane, the goal is to connect them by lines of minimum total length in such a way that any two points may be interconnected by line segments either directly or via other points and line segments.
While the problem is named after Steiner, it has first been posed in 1811 by Joseph 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.
However, although the full Steiner tree problem was formulated in a letter by Gauss, its first serious treatment was in a 1934 paper written in Czech by Vojtěch Jarník and Miloš Kössler [cs].
For general N, the Euclidean Steiner tree problem is NP-hard, and hence it is not known whether an optimal solution can be found by using a polynomial-time algorithm.
However, there is a polynomial-time approximation scheme (PTAS) for Euclidean Steiner trees, i.e., a near-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.
In VLSI 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.
Let G = (V, E) be an undirected graph with non-negative edge weights c and let S ⊆ V be a subset of vertices, called terminals.
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 is APX-complete, i.e., unless P = NP, it is impossible to achieve approximation ratios that are arbitrarily close to 1 in polynomial time.
[13] Karpinski and Alexander Zelikovsky constructed PTAS for the dense instances of Steiner Tree problems.
Algorithms to find the Steiner minimal tree have been found on the sphere, torus, projective plane, wide and narrow cones, and others.
A further well-studied[16] generalization is the survivable 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.
This approximate solution is computable in O(|S| |V|²) polynomial time by first solving the all-pairs shortest paths problem to compute the metric closure, then by solving the minimum spanning tree problem.
Another popular algorithm to approximate the Steiner tree in graphs was published by Takahashi and Matsuyama in 1980.
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 to Kruskal'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 resembling Dijkstra's algorithm but starting from multiple initial vertices.
By using a Heap (data structure) to implement the priority queue and a disjoint-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 the 2 − 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 the 2 − 2/t ratio.
approximation using a linear programming relaxation and a technique called iterative, randomized rounding.
[11] The general graph Steiner tree problem is known to be fixed-parameter tractable, with the number of terminals as a parameter, by the Dreyfus-Wagner algorithm.
[25][26] It is known that the general graph Steiner tree problem does not have a parameterized algorithm running in
, where t is the number of edges of the optimal Steiner tree, unless the Set cover problem has an algorithm running in
parameterized by the number of terminals, it does admit a polynomial-sized approximate kernelization scheme (PSAKS): for any
[29] When parameterizing the graph Steiner tree problem by the number p of non-terminals (Steiner vertices) in the optimum solution, the problem is W[1]-hard (in contrast to the parameterization by the number of terminals, as mentioned above).
