dc.contributor.author Fomin, Fedor dc.contributor.author Kaski, Petteri dc.contributor.author Lokshtanov, Daniel dc.contributor.author Panolan, Fahad dc.contributor.author Saurabh, Saket dc.date.accessioned 2020-07-03T09:34:55Z dc.date.available 2020-07-03T09:34:55Z dc.date.issued 2019 dc.Published Fomin V, Kaski P, Lokshtanov D, Panolan F, Saurabh S. Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree. SIAM Journal on Discrete Mathematics. 2019;33(1):327-345 eng dc.identifier.issn 0895-4801 en_US dc.identifier.issn 1095-7146 en_US dc.identifier.uri https://hdl.handle.net/1956/23311 dc.description.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$, en_US dc.language.iso eng eng dc.publisher Society for Industrial and Applied Mathematics en_US dc.rights Attribution CC BY eng dc.rights.uri http://creativecommons.org/licenses/by/4.0/ eng dc.title Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree en_US dc.type Peer reviewed dc.type Journal article dc.date.updated 2020-02-14T16:26:27Z dc.description.version publishedVersion en_US dc.rights.holder Copyright 2019 SIAM en_US dc.identifier.doi https://doi.org/10.1137/17m1140030 dc.identifier.cristin 1714861 dc.source.journal SIAM Journal on Discrete Mathematics dc.relation.project Norges forskningsråd: 263317
﻿

### This item appears in the following Collection(s)

Except where otherwise noted, this item's license is described as Attribution CC BY