Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree

摘要

In the Steiner tree problem, we are given as input a connected n-vertex graph with edge weights in {1, 2,.... W}, and a subset of 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 O(7.97~k • n~4 • log W) using O(n~3 • log nW • log k) space. This is the first single-exponential time, polynomial-space FPT algorithm for the weighted Steiner Tree problem.