Editing Steiner tree problem (section)

== Parameterized approximation of Steiner tree ==
While the graph Steiner tree problem does not admit a [[Kernelization|polynomial kernel]] unless <math>\textsf{coNP} \subseteq \textsf{NP/poly}</math> parameterized by the number of terminals, it does admit a [[Parameterized approximation algorithm#Approximate kernelization|polynomial-sized approximate kernelization scheme]] (PSAKS): for any <math>\varepsilon>0</math> it is possible to compute a polynomial-sized kernel, which looses only a <math>1+\varepsilon</math> factor in the solution quality.<ref>{{Cite book |last1=Lokshtanov |first1=Daniel |last2=Panolan |first2=Fahad |last3=Ramanujan |first3=M. S. |last4=Saurabh |first4=Saket |title=Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing |chapter=Lossy kernelization |date=2017-06-19 |chapter-url=https://doi.org/10.1145/3055399.3055456 |series=STOC 2017 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=224–237 |doi=10.1145/3055399.3055456 |isbn=978-1-4503-4528-6|s2cid=14599219 |url=http://wrap.warwick.ac.uk/113741/1/WRAP-Lossy-Kernelization-Ramanujan-2019.pdf }}</ref>

When parameterizing the graph Steiner tree problem by the number {{mvar|p}} of non-terminals (Steiner vertices) in the optimum solution, the problem is [[Parameterized complexity#W hierarchy|W[1]-hard]] (in contrast to the parameterization by the number of terminals, as mentioned above). At the same time the problem is [[APX-complete]] and thus does not admit a [[Polynomial-time approximation scheme|PTAS]], unless [[P = NP]]. However, a [[Parameterized approximation algorithm|parameterized approximation scheme]] exists, which for any <math>\varepsilon>0</math> computes a <math>(1+\varepsilon)</math>-approximation in <math>2^{O(p^2/\varepsilon^4)}n^{O(1)}</math> time.<ref name=":0">{{Cite journal |last1=Dvořák |first1=Pavel |last2=Feldmann |first2=Andreas E. |last3=Knop |first3=Dušan |last4=Masařík |first4=Tomáš |last5=Toufar |first5=Tomáš |last6=Veselý |first6=Pavel |date=2021-01-01 |title=Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices |url=https://epubs.siam.org/doi/10.1137/18M1209489 |journal=SIAM Journal on Discrete Mathematics |volume=35 |issue=1 |pages=546–574 |doi=10.1137/18M1209489 |s2cid=3581913 |issn=0895-4801|arxiv=1710.00668 }}</ref> Also a PSAKS exists for this parameterization.<ref name=":0" />