Parameterized single-exponential time polynomial space algorithm for steiner tree
Loading...
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
Date
2019
Department
University of Bergen
Professorship Kaski Petteri
University of California Santa Barbara
Homi Bhabha National Institute
Department of Computer Science
Professorship Kaski Petteri
University of California Santa Barbara
Homi Bhabha National Institute
Department of Computer Science
Major/Subject
Mcode
Degree programme
Language
en
Pages
19
327-345
327-345
Series
SIAM Journal on Discrete Mathematics, Volume 33, issue 1
Abstract
In the Steiner Tree problem, we are given as input a connected n-vertex graph with edge weights in \{ 1, 2, . . ., 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 O (7.97 k · n 4 · log W) and 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. 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 O (6.751 k n 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 ε > 0 there is an n O (f(ε )) log W space 4 (1+ ε ) k n O (f(ε )) log W time algorithm for Steiner Tree, where f is a computable function depending only on ε .Description
| openaire: EC/H2020/338077/EU//TAPEASE | openaire: EC/H2020/306992/EU//PARAPPROX
Keywords
Steiner tree, FPT algorithm, recurrence relation
Other note
Citation
Fomin , F , Kaski , P , Lokshtanov , D , Panolan , F & Saurabh , S 2019 , ' Parameterized single-exponential time polynomial space algorithm for steiner tree ' , SIAM Journal on Discrete Mathematics , vol. 33 , no. 1 , pp. 327-345 . https://doi.org/10.1137/17M1140030
