Input description: A graph G=(V,E). A subset of vertices .
Problem description: Find the smallest tree connecting all the vertices of T.
Discussion: Steiner tree often arises in network design and wiring layout problems. Suppose we are given a set of sites that must be connected by wires as cheaply as possible. The minimum Steiner tree describes the way to connect them using the smallest amount of wire. Analogous problems arise in designing networks of water pipes or heating ducts in buildings. Similar considerations also arise in VLSI circuit layout, where we seek to connect a set of sites to (say) ground under constraints such as material cost, signal propagation time, or reducing capacitance.
The Steiner tree problem is distinguished from the minimum spanning tree problem (see Section ) in that we are permitted to construct or select intermediate connection points to reduce the cost of the tree. Issues in Steiner tree construction include:
Still, Steiner tree remains a hard problem. Through exhaustive search methods, instances as large as 32 points for the Euclidean and 30 for the rectilinear problems can be confidently solved to optimality. We recommend experimenting with the implementations described below before attempting your own.
Many different phylogenic tree construction algorithms have been developed, which vary in the data they attempt to model and what the desired optimization criterion is. Because they all give different answers, identifying the correct algorithm for a given application is somewhat a matter of faith. A reasonable procedure is to acquire a standard package of implementations, discussed below, and then see what happens to your data under all of them.
Fortunately, there is a good, efficient heuristic for finding Steiner trees that works well on all versions of the problem. Construct a graph modeling your input, with the weight of edge (i,j) equal to the distance from point i to point j. Find a minimum spanning tree of this graph. You are guaranteed a provably good approximation for both Euclidean and rectilinear Steiner trees.
The worst case for a minimum spanning tree approximation of the Euclidean distance problem is three points forming an equilateral triangle. The minimum spanning tree will contain two of the sides (for a length of 2), whereas the minimum Steiner tree will connect the three points using an interior point, for a total length of . This ratio of is always achieved, and in practice the easily-computed minimum spanning tree is usually within a few percent of the optimal Steiner tree. For rectilinear Steiner trees, the ratio with rectilinear minimum spanning trees is always .
Such a minimum spanning tree can be refined by inserting a Steiner point whenever the edges of the minimum spanning tree incident on a vertex form an angle of less than 120 degrees between them. Inserting these points and locally readjusting the tree edges can move the solution a few more percent towards the optimum. Similar optimizations are possible for rectilinear spanning trees.
An alternative heuristic for graphs is based on shortest path. Start with a tree consisting of the shortest path between two terminals. For each remaining terminal t, find the shortest path to a vertex v in the tree and add this path to the tree. The time complexity and quality of this heuristic depend upon the insertion order of the terminals and how the shortest-path computations are performed, but something simple and fairly effective is likely to result.
Implementations: Salowe and Warme [SW95] have developed a program for computing exact rectilinear Steiner minimal trees. It is available by anonymous ftp from ftp.cs.virginia.edu in the directory pub/french/salowe/newsteiner.tar.Z. It should be capable of handling up to 30 points routinely. A heuristic program by Robins and Zhang is available from the algorithm repository http://www.cs.sunysb.edu/ algorith.
PHYLIP is an extensive and widely used package of programs for inferring phylogenic trees. It contains over twenty different algorithms for constructing phylogenic trees from data. Although many of them are designed to work with molecular sequence data, several general methods accept arbitrary distance matrices as input. With versions written in C and Pascal, it is available on the WWW from http://evolution.genetics.washington.edu/phylip.html.
Notes: The most complete reference on the Steiner tree problem is the monograph by Hwang, Richards, and Winter [HRW92]. Surveys on the problem include [Kuh75]. Steiner tree problems arising in VLSI design are discussed in [KPS89, Len90]. Empirical results on Steiner tree heuristics include [SFG82, Vos92].
The Euclidean Steiner problem dates back to Fermat, who asked how to find a point p in the plane minimizing the sum of the distances to three given points. This was solved by Torricelli before 1640. Steiner was apparently one of several mathematicians who worked the general problem for n points, and he was mistakenly credited with the problem. An interesting, more detailed history appears in [HRW92].
Gilbert and Pollak [GP68] first conjectured that the ratio of the length of the minimum Steiner tree over the minimum spanning tree is always . After twenty years of active research, the Gilbert-Pollak ratio was finally proven by Du and Hwang [DH92]. The Euclidean minimum spanning tree for n points in the plane can be constructed in time [PS85].
Expositions on the proof that the Steiner tree problem for graphs is hard [Kar72] include [Eve79a]. Expositions on exact algorithms for Steiner trees in graphs include [Law76]. The hardness of Steiner tree for Euclidean and rectilinear metrics was established in [GGJ77, GJ77]. Euclidean Steiner tree is not known to be in NP, because of numerical issues in representing distances.
Analogies can be drawn between minimum Steiner trees and minimum energy configurations in certain physical systems. The case that such analog systems, including the behavior of soap films over wire frames, ``solve'' the Steiner tree problem is discussed in [Mie58].
Related Problems: Minimum spanning tree (see page ), shortest path (see page ).