Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree

In the Steiner tree problem, we are given as input a connected

$$n$$

n

-vertex graph with edge weights in

$$\{1,2,\ldots ,W\}$$

{

1

,

2

,

…

,

W

}

, and a subset of

$$k$$

k

terminal vertices. Our task is to compute a minimum-weight tree that contains all the terminals. We give an algorithm for this problem with running time

$${\mathcal O}(7.97^k\cdot n^4\cdot \log {W})$$

O

(

7

.

97

k

·

n

4

·

log

W

)

using

$${\mathcal O}(n^3\cdot \log {nW} \cdot \log k)$$

O

(

n

3

·

log

n

W

·

log

k

)

space. This is the first single-exponential time, polynomial-space FPT algorithm for the weighted

Steiner Tree

problem.