Steiner tree problem

Steiner tree for three points A, B, and C (note there are no direct connections between A, B, C). The Steiner point S is located at the Fermat point of the triangle ABC.
Solution for four points—there are two Steiner points, S1 and S2

The Steiner tree problem, motorway problem, or minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects.

The Steiner tree problem is superficially similar to the minimum spanning tree problem: given a set V of points (vertices), interconnect them by a network (graph) of shortest length, where the length is the sum of the lengths of all edges. The difference between the Steiner tree problem and the minimum spanning tree problem is that, in the Steiner tree problem, extra intermediate vertices and edges may be added to the graph in order to reduce the length of the spanning tree. These new vertices introduced to decrease the total length of connection are known as Steiner points or Steiner vertices. It has been proved that the resulting connection is a tree, known as the Steiner tree. There may be several Steiner trees for a given set of initial vertices.

The Steiner tree problem has applications in circuit layout or network design. Most versions of the Steiner tree problem are NP-complete. In fact, one of these was among Karp's original 21 NP-complete problems. Some restricted cases can be solved in polynomial time. In practice, heuristics are used.

Euclidean Steiner tree

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.

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.

For the Euclidean Steiner problem, points added to the graph (Steiner points) must have a degree of three, and the three edges incident to such a point must form three 120 degree angles (see Fermat point). It follows that the maximum number of Steiner points that a Steiner tree can have is N − 2, where N is the initial number of given points.

For N = 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 the Fermat point; otherwise the solution is given by the two sides of the triangle which meet on the angle with 120 or more degrees.

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.[1] It is not known whether the Euclidean Steiner tree problem is NP-complete, since membership to the complexity class NP is not known.

Rectilinear Steiner tree

The minimum rectilinear Steiner tree problem (MRST) is a variant of the geometric Steiner tree problem in the plane, in which the Euclidean distance is replaced with the rectilinear distance. The problem arises in the physical design of electronic design automation. 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.[2]

Generalization of minimum Steiner tree

Steiner trees have also been studied in the context of weighted graphs. In the general Steiner tree problem (Steiner tree in graphs), we are given an edge-weighted graph G = (V, E, w) and a subset S ⊆ V of required vertices. A Steiner tree is a tree in G that spans all vertices of S. There are two versions of the problem: in the optimization problem associated with Steiner trees, the task is to find a minimum-weight Steiner tree; in the decision problem, we are given a value k and the task is to determine whether a Steiner tree of total weight at most k exists. The decision problem was one of Karp's 21 NP-complete problems; hence the optimization problem is NP-hard.

A special case of this problem is when G is a complete graph, each vertex v ∈ V corresponds to a point in a metric space, and the edge weights w(e) for each e ∈ E correspond to distances in the space. Put otherwise, the edge weights satisfy the triangle inequality. This variant is known as the metric 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.[3]

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. There is a polynomial-time algorithm that approximates the minimum Steiner tree to within a factor of\ln(4) + \epsilon\approx1.386;[4] however, approximating within a factor 96/95\approx 1.0105 is NP-hard.[5] For the restricted case of Steiner Tree problem with distances 1 and 2, a 1.25-approximation algorithm is known.[6]

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

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.[7]

Another generalizations of the Steiner tree problem are the k-edge-connected Steiner network problem and the k-vertex-connected Steiner network problem, where the goal is to find a k-edge-connected graph or a k-vertex-connected graph rather than any connected graph.

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

Approximating the Steiner Tree

In the general graph Steiner tree problem, a minimum-cost terminal spanning tree is a minimum spanning tree (MST) on the graph induced by the set of terminals R on the metric closure G_m of G. This tree is a feasible but not necessarily optimal solution to the Steiner tree problem. This metric closure G_m can be substituted for G without loss of generality, and is described by placing an edge in G_m between every two vertices with weight equal to the shortest path between those vertices in the original graph. There are |V|*(|V|-1)/2 =O(|V|^2) such vertices, so this closure can be produced in polynomial time by applying Djikstra's algorithm on every pair of vertices. It is trivial to prove that the optimal solution on G_M, Opt_{G_M} is of equal cost to the that of the optimal solution Opt_G on G

The minimum cost terminal spanning tree is the spanning tree on the (fully connected) subgraph of the metric closure containing only the terminals as vertices and the edges between them. This tree is well-known to be a 2-approximation for the optimal minimum Steiner tree. More specifically, it is a 2-2/|R|approximation where |R| is the number of terminals. This proof can be worked out by considering a traveling salesman tour on the optimal Steiner tree.

A series of papers, culminating with Robins and Zelikovsky's famous algorithm in 2000 improved this ratio to 1.55 by iteratively improving upon the minimum cost terminal spanning tree. More recently, however, Jaroslaw Byrka et al. proved an \ln(4) + \epsilon \le 1.39 approximation using a linear programming relaxation and a technique called iterative, randomized rounding.[4]

Steiner ratio

The Steiner ratio is the supremum 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.[9]

In the Euclidean Steiner tree problem, the Steiner ratio is conjectured to be \frac{2}{\sqrt{3}}. Despite earlier claims of a proof,[10] the conjecture is still open.[11] In the Rectilinear Steiner tree problem, the Steiner ratio is \frac{3}{2}.[12]

See also

Notes

  1. ↑ Crescenzi et al. (2000).
  2. ↑ Sherwani (1993), p. 228.
  3. ↑ Vazirani (2003), pp. 27–28.
  4. 1 2 Byrka et al. (2010).
  5. ↑ Chlebík & Chlebíková (2008).
  6. ↑ Berman, Karpinski & Zelikovsky (2009).
  7. ↑ Smith & Winter (1995), p. 361.
  8. ↑ Paolini & Stepanov (2012).
  9. ↑ Ganley (2004).
  10. ↑ The New York Times, Oct 30, 1990, reported that a proof had been found, and that Ronald Graham, who had offered $500 for a proof, was about to mail a check to the authors.
  11. ↑ Ivanov & Tuzhilin (2012).
  12. ↑ Hwang (1976).

References

  • Berman, Piotr; Karpinski, Marek; Zelikovsky, Alexander (2009). "1.25-approximation algorithm for Steiner tree problem with distances 1 and 2". Algorithms and Data Structures: 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009, Proceedings. Lecture Notes in Computer Science. pp. 86–97. doi:10.1007/978-3-642-03367-4_8. 
  • Bern, Marshall W.; Graham, Ronald L. (1989). "The shortest-network problem". Scientific American 260 (1): 84–89. doi:10.1038/scientificamerican0189-84. 
  • Byrka, J.; Grandoni, F.; Rothvoß, T.; Sanita, L. (2010). "An improved LP-based approximation for Steiner tree". Proceedings of the 42nd ACM Symposium on Theory of Computing. pp. 583–592. doi:10.1145/1806689.1806769. 
  • Chlebík, Miroslav; Chlebíková, Janka (2008). "The Steiner tree problem on graphs: Inapproximability results". Theoretical Computer Science. doi:10.1016/j.tcs.2008.06.046. 
  • Cieslik, Dietmar (1998). Steiner Minimal Trees. p. 319. ISBN 0-7923-4983-0. 
  • Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000). "Minimum geometric Steiner tree". A Compendium of NP Optimization Problems. 
  • Ganley, Joseph L. (2004). "Steiner ratio". In Black, Paul E. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved 2012-05-24. 
  • Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5 , pp. 208–209, problems ND12 and ND13.
  • Hwang, F. K. (1976). "On Steiner minimal trees with rectilinear distance". SIAM Journal on Applied Mathematics 30 (1): 104–114. doi:10.1137/0130013. 
  • Hwang, F. K.; Richards, D. S.; Winter, P. (1992). The Steiner Tree Problem. Annals of Discrete Mathematics 53. North-Holland: Elsevier. ISBN 0-444-89098-X. 
  • Ivanov, Alexander; Tuzhilin, Alexey (1994). Minimal Networks: The Steiner Problem and Its Generalizations. N.W., Boca Raton, Florida: CRC Press. ISBN 978-0-8493-8642-8. 
  • Ivanov, Alexander; Tuzhilin, Alexey (2000). Branching solutions to one-dimensional variational problems. Singapore-New Jersey-London-Hong Kong: World Scientific. ISBN 978-981-02-4060-8. 
  • Ivanov, Alexander; Tuzhilin, Alexey (2003). Extreme Networks Theory (in Russian). Moscow-Izhevsk: Institute of Computer Investigations. ISBN 5-93972-292-X. 
  • Ivanov, Alexander; Tuzhilin, Alexey (2012). "The Steiner ratio Gilbert–Pollak conjecture is still open: Clarification statement". Algorithmica 62 (1-2): 630–632. doi:10.1007/s00453-011-9508-3. 
  • Ivanov, Alexander; Tuzhilin, Alexey (2015). "Branched coverings and Steiner ratio". International Transactions in Operational Research (ITOR). doi:10.1111/itor.12182. 
  • Korte, Bernhard; Vygen, Jens (2006). "Section 20.1". Combinatorial Optimization: Theory and Algorithms (3rd ed.). Springer. ISBN 3-540-25684-9. 
  • Paolini, E.; Stepanov, E. (2012). "Existence and regularity results for the Steiner problem". Calc. Var. Partial Diff. Equations. doi:10.1007/s00526-012-0505-4. 
  • Robins, Gabriel; Zelikovsky, Alexander (2000). "Improved Steiner Tree Approximation in Graphs". Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00). Philadelphia, PA, USA: Society for Industrial and Applied Mathematics. pp. 770–779. ISBN 0-89871-453-2. 
  • Sherwani, Naveed A. (1993). Algorithms for VLSI Physical Design Automation. Kluwer Academic Publishers. ISBN 9781475722192. 
  • Smith, J. M.; Winter, P. (1995). "Computational geometry and topological network design". In Du, Ding-Zhu; Hwang, Frank. Computing in Euclidean geometry. Lecture Notes Series on Computing 4 (2nd ed.). River Edge, NJ: World Scientific Publishing Co. pp. 351–451. ISBN 981-02-1876-1. 
  • Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3-540-65367-8. 
  • Wu, Bang Ye; Chao, Kun-Mao (2004). "Chapter 7". Spanning Trees and Optimization Problems. Chapman & Hall/CRC. ISBN 1-58488-436-3. 

External links

Wikimedia Commons has media related to Steiner tree problem.
This article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.