Steiner Tree

  

 

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:

• How many points do you have to connect? - The Steiner tree of a pair of vertices is simply the shortest path between them (see Section ). The Steiner tree of all the vertices, when S=V, simply defines the minimum spanning tree of G. Despite these special cases, the general minimum Steiner tree problem is NP-hard and remains so under a broad range of restrictions.
• Is the input a set of geometric points or a distance graph? -   Geometric versions of Steiner tree take as input a set of points, typically in the plane, and seek the smallest tree connecting the points. A complication is that the set of possible intermediate points is not given as part of the input but must be deduced from the set of points. These possible Steiner points must satisfy several geometric properties, which can be used to reduce the set of candidates down to a finite number. For example, every Steiner point will have degree exactly three in a minimum Steiner tree, and the angles formed between any two of these edges will be exactly 120 degrees.
• Are there constraints on the edges we can use? - Many wiring problems correspond to geometric versions of the problem where all edges are restricted to being either horizontal or vertical, which is the so-called rectilinear Steiner problem.   A different set of angular and degree conditions applies for rectilinear Steiner trees than for Euclidean trees. In particular, all angles must be multiples of 90 degrees, and each vertex is of degree up to four.
• Do I really need an optimal tree? - In certain applications, such as minimum cost communications networks, construction costs are high enough to invest large amounts of computation in finding the best possible Steiner tree.   This implies an exhaustive search technique such as backtracking or branch-and-bound.   There are many opportunities for pruning search based on geometric constraints. For graph instances, network reduction procedures can reduce the problem to a graph typically one-quarter the size of the input graph.

  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.

• How can I reconstruct Steiner vertices I never knew about? - A very special type of Steiner tree arises in classification and evolution. A phylogenic tree illustrates the relative similarity between different objects or species. Each object represents (typically) a terminal vertex of the tree, with intermediate vertices representing branching points between classes of objects. For example, an evolutionary tree of animal species might have leaf nodes including (human, dog, snake) and internal nodes corresponding to the taxa (animal, mammal, reptile). A tree rooted at animal with dog and human classified under mammal implies that humans are closer to dogs than to snakes.    

  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 ).