Editing Steiner tree problem (section)

{{Short description|On short connecting networks with added vertices}}
{{Use dmy dates|date=May 2022}}
[[File:Steiner 3 points.svg|thumb|Steiner tree for three points {{mvar|A}}, {{mvar|B}}, and {{mvar|C}} (note there are no direct connections between {{mvar|A}}, {{mvar|B}}, {{mvar|C}}). The Steiner point {{mvar|S}} is located at the [[Fermat point]] of the [[triangle]] {{mvar|ABC}}.]]
[[File:Steiner 4 points.svg|thumb|Solution for four points—there are two Steiner points, {{math|''S''{{sub|1}}}} and {{math|''S''{{sub|2}}}}]]

In [[combinatorial mathematics]], the '''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 (graph theory)|tree]] of minimum weight that contains all terminals (but may include additional vertices) and minimizes the total weight of its edges. Further well-known variants are the ''Euclidean Steiner tree problem'' and the ''[[Rectilinear Steiner tree|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|minimum spanning tree problem]]. If a Steiner tree problem in graphs contains exactly two terminals, it reduces to finding the 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]], no such solution is known for the Steiner tree problem. Its [[Decision problem|decision variant]], asking whether a given input has a tree of weight less than some given threshold, is [[NP-complete]], which implies that the optimization variant, asking for the minimum-weight tree in a given graph, is [[NP-hardness|NP-hard]]. In fact, the decision variant was among [[Karp's 21 NP-complete problems|Karp's original 21 NP-complete problems]]. The Steiner tree problem in graphs has applications in [[Electrical network|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.{{sfnp|Rehfeldt|Koch|2023}}{{sfnp|Juhl|Warme|Winter |Zachariasen|2018}}