Show simple item record

dc.contributor.authorFomin, Fedor
dc.contributor.authorKaski, Petteri
dc.contributor.authorLokshtanov, Daniel
dc.contributor.authorPanolan, Fahad
dc.contributor.authorSaurabh, Saket
dc.PublishedFomin 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-345eng
dc.description.abstractIn 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.publisherSociety for Industrial and Applied Mathematicsen_US
dc.rightsAttribution CC BYeng
dc.titleParameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Treeen_US
dc.typePeer reviewed
dc.typeJournal article
dc.rights.holderCopyright 2019 SIAMen_US
dc.source.journalSIAM Journal on Discrete Mathematics
dc.relation.projectNorges forskningsråd: 263317

Files in this item


This item appears in the following Collection(s)

Show simple item record

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