Editing Steiner tree problem (section)

==Steiner tree in graphs and variants==
Steiner trees have been extensively studied in the context of [[weighted graph]]s. The prototype is, arguably, the '''Steiner tree problem''' '''in graphs'''. Let {{math|1=''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'')}} be an undirected graph with non-negative edge weights c and let {{math|1=''S''&nbsp;⊆&nbsp;''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 integers 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]]. Steiner tree problems in graphs are applied to various problems in research and industry,<ref>{{Cite journal|last=Ljubić|first=Ivana|date=2021|title=Solving Steiner trees: Recent advances, challenges, and perspectives|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/net.22005|journal=Networks|language=en|volume=77|issue=2|pages=177–204|doi=10.1002/net.22005|s2cid=229458488 |issn=1097-0037}}</ref> including multicast routing<ref>{{Cite journal|last1=Novak|first1=Roman|last2=Rugelj|first2=Joz̆e|last3=Kandus|first3=Gorazd|date=2001-10-01|title=A note on distributed multicast routing in point-to-point networks|url=https://www.sciencedirect.com/science/article/pii/S0305054800000290|journal=Computers & Operations Research|language=en|volume=28|issue=12|pages=1149–1164|doi=10.1016/S0305-0548(00)00029-0|issn=0305-0548}}</ref> and bioinformatics.<ref>{{Cite journal|last1=Klimm|first1=Florian|last2=Toledo|first2=Enrique M.|last3=Monfeuga|first3=Thomas|last4=Zhang|first4=Fang|last5=Deane|first5=Charlotte M.|last6=Reinert|first6=Gesine|date=2020-11-02|title=Functional module detection through integration of single-cell RNA sequencing data with protein–protein interaction networks|journal=BMC Genomics|volume=21|issue=1|pages=756|doi=10.1186/s12864-020-07144-2|issn=1471-2164|pmc=7607865|pmid=33138772 |doi-access=free }}</ref>

A special case of this problem is when ''G'' is a [[complete graph]], each vertex {{math|1=''v''&nbsp;∈&nbsp;''V''}} corresponds to a point in a [[metric space]], and the edge weights ''w''(''e'') for each ''e''&nbsp;∈&nbsp;''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.{{sfnp|Vazirani|2003|pp=27–28}}

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 [[Approximation algorithm|approximates]] the minimum Steiner tree to within a factor of <math>\ln(4) + \varepsilon\approx1.386</math>;{{sfnp|Byrka|Grandoni|Rothvoß|Sanita|2010}}
however, approximating within a factor <math>96/95\approx 1.0105</math> is NP-hard.{{sfnp|Chlebík|Chlebíková|2008}} For the restricted case of Steiner Tree problem with distances 1 and 2, a 1.25-approximation algorithm is known.{{sfnp|Berman|Karpinski|Zelikovsky|2009}} Karpinski and [[Alexander Zelikovsky]] constructed PTAS for the dense instances of Steiner Tree problems.{{sfnp|Karpinski|Zelikovsky|1998}}

In a special case of the graph problem, the Steiner tree problem for [[quasi-bipartite graph]]s, ''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.{{sfnp|Smith|Winter|1995|p=361}}

Other 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|''k''-edge-connected graph]] or a [[k-vertex-connected graph|''k''-vertex-connected graph]] rather than any connected graph. A further well-studied<ref>{{Cite journal |last1=Kerivin |first1=Hervé |last2=Mahjoub |first2=A. Ridha |date=2005 |title=Design of Survivable Networks: A survey |url=https://onlinelibrary.wiley.com/doi/10.1002/net.20072 |journal=Networks |language=en |volume=46 |issue=1 |pages=1–21 |doi=10.1002/net.20072 |s2cid=8165318 |issn=0028-3045}}</ref> generalization is the '''survivable network design problem (SNDP)''' where the task is to connect each vertex pair with a given number (possibly 0) of edge- or vertex-disjoint paths.

The Steiner problem has also been stated in the general setting of metric spaces and for possibly infinitely many points.{{sfnp|Paolini|Stepanov|2012}}