Editing Steiner tree problem (section)

==Parameterized complexity of Steiner tree==

The general graph Steiner tree problem is known to be [[Parameterized complexity#FPT|fixed-parameter tractable]], with the number of terminals as a parameter, by the Dreyfus-Wagner algorithm.{{sfnp|Dreyfus|Wagner|1971}}{{sfnp|Levin|1971}} The running time of the Dreyfus-Wagner algorithm is <math>3^{|S|} \text{poly}(n)</math>, where {{mvar|n}} is the number of vertices of the graph and {{mvar|S}} is the set of terminals. Faster algorithms exist, running in <math>c^{|S|} \text{poly}(n)</math> time for any <math>c > 2</math> or, in the case of small weights, <math>2^{|S|} \text{poly}(n) W</math> time, where {{mvar|W}} is the maximum weight of any edge.{{sfnp|Fuchs|Kern|Mölle|Richter|2007}}{{sfnp|Björklund|Husfeldt|Kaski|Koivisto|2007}} A disadvantage of the aforementioned algorithms is that they use [[Space complexity|exponential space]]; there exist polynomial-space algorithms running in <math>2^{|S|} \text{poly}(n) W</math> time and <math>(7.97)^{|S|} \text{poly}(n) \log W</math> time.{{sfnp|Lokshtanov|Nederlof|2010}}{{sfnp|Fomin|Kaski|Lokshtanov|Panolan|2015}}

It is known that the general graph Steiner tree problem does not have a parameterized algorithm running in <math>2^{\epsilon t} \text{poly}(n)</math> time for any <math>\epsilon < 1</math>, where {{mvar|t}} is the number of edges of the optimal Steiner tree, unless the [[Set cover problem]] has an algorithm running in <math>2^{\epsilon n} \text{poly}(m)</math> time for some <math>\epsilon < 1</math>, where {{mvar|n}} and {{mvar|m}} are the number of elements and the number of sets, respectively, of the instance of the set cover problem.{{sfnp|Cygan|Dell|Lokshtanov|Marx|2016}} Furthermore, it is known that the problem does not admit a [[Kernelization|polynomial kernel]] unless <math>\textsf{coNP} \subseteq \textsf{NP/poly}</math>, even parameterized by the number of edges of the optimal Steiner tree and if all edge weights are 1.{{sfnp|Dom|Lokshtanov|Saurabh|2014}}