Steiner tree problem

Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial 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 predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals (but may include additional vertices). Further well-known variants are the Euclidean Steiner tree problem and the rectilinear 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 the minimum spanning tree problem. If a Steiner tree problem in graphs contains exactly two terminals, it reduces to finding a 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 in polynomial time, the decision variant of the Steiner tree problem in graphs is NP-complete (which implies that the optimization variant is NP-hard); in fact, the decision variant was among Karp's original 21 NP-complete problems. 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. Despite the pessimistic worst-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]

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.

The problem for N = 3 has long been considered, and quickly extended to the problem of finding a star network with a single hub connecting to all of the N given points, of minimum total length. 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]. 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.^[3]

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.^[4] 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 rectilinear Steiner tree problem 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.^[5]

Steiner tree in graphs and variants

Steiner trees have been extensively studied in the context of weighted graphs. The prototype is, arguably, the Steiner tree problem in graphs. 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. A Steiner tree is a tree in G that spans 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 the edge weights are integer and the task is to determine whether a Steiner tree exists whose total weight does not exceed a predefined natural number k. The decision problem is 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.^[6]

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)+\varepsilon \approx 1.386$ ;^[7] however, approximating within a factor $96/95\approx 1.0105$ is NP-hard.^[8] For the restricted case of Steiner Tree problem with distances 1 and 2, a 1.25-approximation algorithm is known.^[9]

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

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

Approximating the Steiner tree

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. The metric closure of a graph G is the complete graph in which each edge is weighted by the shortest path distance between the nodes in G. This algorithm produces a tree whose weight is within a 2 − 2/t factor of the weight of the optimal Steiner tree; this can be proven by considering a traveling salesperson tour on the optimal Steiner tree. The approximate solution is computable in polynomial time by first solving the all-pairs shortest paths problem to compute the metric closure, then by solving the minimum spanning tree problem.

A series of papers provided approximation algorithms for the minimum Steiner tree problem with approximation ratios that improved upon the 2 − 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, Jaroslaw Byrka et al. proved an $\ln(4)+\varepsilon \leq 1.39$ approximation using a linear programming relaxation and a technique called iterative, randomized rounding.^[7]

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

In the Euclidean Steiner tree problem, the Steiner ratio is conjectured to be ${\tfrac {2}{\sqrt {3}}}\approx 1.1547$ , the ratio that is achieved by three points in an equilateral 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,^[13] the conjecture is still open.^[14] The best widely-accepted upper bound for the problem is 1.2134, by Chung & Graham (1985).

For the rectilinear Steiner tree problem, the Steiner ratio is exactly ${\tfrac {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.^[15] More precisely, for $L_{1}$ distance the square should be tilted at $45^{\circ }$ with respect to the coordinate axes, while for $L_{\infty }$ distance the square should be axis-aligned.

Notes

^ "Report by Polzin and Vahdati Daneshmand" (PDF). Retrieved 11 November 2016.
^ Juhl et al. (2014).
^ Korte, Bernhard; Nešetřil, Jaroslav (2001), "Vojtěch Jarnik's work in combinatorial optimization", Discrete Mathematics, 235 (1–3): 1–17, doi:10.1016/S0012-365X(00)00256-9, MR 1829832.
^ Crescenzi et al. (2000).
^ Sherwani (1993), p. 228.
^ Vazirani (2003), pp. 27–28.
^ ^a ^b Byrka et al. (2010).
^ Chlebík & Chlebíková (2008).
^ Berman, Karpinski & Zelikovsky (2009).
^ Smith & Winter (1995), p. 361.
^ Paolini & Stepanov (2012).
^ Ganley (2004).
^ 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.
^ Ivanov & Tuzhilin (2012).
^ 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. Vol. 5664. pp. 86–97. doi:10.1007/978-3-642-03367-4_8. {{cite conference}}: Invalid |ref=harv (help)
Bern, Marshall W.; Graham, Ronald L. (1989). "The shortest-network problem". Scientific American. 260 (1): 84–89. Bibcode:1989SciAm.260a..84B. doi:10.1038/scientificamerican0189-84. {{cite journal}}: Invalid |ref=harv (help)
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. CiteSeerX 10.1.1.177.3565. doi:10.1145/1806689.1806769. {{cite conference}}: Invalid |ref=harv (help)
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. {{cite journal}}: Invalid |ref=harv (help)
Chung, F. R. K.; Graham, R. L. (1985). "A new bound for Euclidean Steiner minimal trees". Discrete geometry and convexity (New York, 1982). Annals of the New York Academy of Science. Vol. 440. New York: New York Academy of Science. pp. 328–346. Bibcode:1985NYASA.440..328C. doi:10.1111/j.1749-6632.1985.tb14564.x. MR 0809217. {{cite conference}}: Invalid |ref=harv (help)
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. {{cite web}}: Invalid |ref=harv (help)
Ganley, Joseph L. (2004). "Steiner ratio". In Black, Paul E. (ed.). Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved 24 May 2012. {{cite book}}: Invalid |ref=harv (help)
Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676., 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. {{cite journal}}: Invalid |ref=harv (help)
Hwang, F. K.; Richards, D. S.; Winter, P. (1992). The Steiner Tree Problem. Annals of Discrete Mathematics. Vol. 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. {{cite journal}}: Invalid |ref=harv (help)
Ivanov, Alexander; Tuzhilin, Alexey (2015). "Branched coverings and Steiner ratio". International Transactions in Operational Research (ITOR). arXiv:1412.5433. doi:10.1111/itor.12182. {{cite journal}}: Invalid |ref=harv (help)
Juhl, D.; Warme, D.M.; Winter, P.; Zachariasen, M. (2014). "The GeoSteiner Software Package for computing Steiner trees in the plane: an updated computational study". Proceedings of the 11th DIMACS Implementation Challenge (PDF). {{cite conference}}: Invalid |ref=harv (help)
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. {{cite journal}}: Invalid |ref=harv (help)
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. {{cite book}}: Invalid |ref=harv (help)
Smith, J. M.; Winter, P. (1995). "Computational geometry and topological network design". In Du, Ding-Zhu; Hwang, Frank (eds.). Computing in Euclidean geometry. Lecture Notes Series on Computing. Vol. 4 (2nd ed.). River Edge, NJ: World Scientific Publishing Co. pp. 351–451. ISBN 981-02-1876-1. {{cite book}}: Invalid |ref=harv (help)
Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3-540-65367-8. {{cite book}}: Invalid |ref=harv (help)
Wu, Bang Ye; Chao, Kun-Mao (2004). "Chapter 7". Spanning Trees and Optimization Problems. Chapman & Hall/CRC. ISBN 1-58488-436-3.

External links

Hazewinkel, M. (2001) [1994], "Steiner tree problem", Encyclopedia of Mathematics, EMS Press
M. Hauptmann, M. Karpinski (2013): A Compendium on Steiner Tree Problems
GeoSteiner (Euclidean and rectilinear Steiner tree solver; Source available, for non commercial use)
SCIP-Jack (Solver for the Steiner tree problem in graphs and 11 variants; Source available, free for academic use)
https://archive.org/details/RonaldLG1988 (Movie: Ronald L Graham: The Shortest Network Problem (1988)
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)
"Using Steiner Trees to Minimize Average Completion Times of Bulk Data Transfers", DCCast: Efficient Point to Multipoint Transfers Across Datacenters, USENIX Association

[1] "Report by Polzin and Vahdati Daneshmand" (PDF). Retrieved 11 November 2016.

[FOOTNOTEJuhlWarmeWinterZachariasen2014-2] Juhl et al. (2014).

[3] Korte, Bernhard; Nešetřil, Jaroslav (2001), "Vojtěch Jarnik's work in combinatorial optimization", Discrete Mathematics, 235 (1–3): 1–17, doi:10.1016/S0012-365X(00)00256-9, MR 1829832.

[FOOTNOTECrescenziKannHalldórssonKarpinski2000-4] Crescenzi et al. (2000).

[FOOTNOTESherwani1993228-5] Sherwani (1993), p. 228.

[FOOTNOTEVazirani200327–28-6] Vazirani (2003), pp. 27–28.

[FOOTNOTEByrkaGrandoniRothvoßSanita2010-7] Byrka et al. (2010).

[FOOTNOTEChlebíkChlebíková2008-8] Chlebík & Chlebíková (2008).

[FOOTNOTEBermanKarpinskiZelikovsky2009-9] Berman, Karpinski & Zelikovsky (2009).

[FOOTNOTESmithWinter1995361-10] Smith & Winter (1995), p. 361.

[FOOTNOTEPaoliniStepanov2012-11] Paolini & Stepanov (2012).

[FOOTNOTEGanley2004-12] Ganley (2004).

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

[FOOTNOTEIvanovTuzhilin2012-14] Ivanov & Tuzhilin (2012).

[FOOTNOTEHwang1976-15] Hwang (1976).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]