Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree

Abstract

In the Steiner Tree problem, we are given as input a connected \(n\)-vertex graph with edge weights in \(\{1,2,\ldots,W\}\), and a set of \(k\) terminal vertices. Our task is to compute a minimum-weight tree that contains all of the terminals. The main result of the paper is an algorithm solving Steiner Tree in time \(\mathcal{O}(7.97^k\cdot n^4\cdot \log{W})\) and using \(\mathcal{O}(n^3\cdot \log{nW} \cdot \log k)\) space. This is the first single-exponential time, polynomial space FPT algorithm for the weighted Steiner Tree problem. Whereas our main result seeks to optimize the polynomial dependency in \(n\) for both the running time and space usage, it is possible to trade between polynomial dependence in \(n\) and the single-exponential dependence in \(k\) to obtain faster running time as a function of \(k\), but at the cost of increased running time and space usage as a function of \(n\), In particular, we show that there exists a polynomial space algorithm for Steiner Tree running in \(\mathcal{O}(6.751^kn^{O(1)}\log W)\) time. Finally, by pushing such a trade-off between a polynomial in \(n\) and an exponential in \(k\) dependencies, we show that for any \(\epsilon>0\) there is an \(n^{\mathcal{O}(f(\epsilon))}\log W\) space \(4^{(1+\epsilon)k}n^{\mathcal{O}(f(\epsilon))}\log W\) time algorithm for Steiner Tree, where \(f\) is a computable function depending only on \(\epsilon\),