Parameterized single-exponential time polynomial space algorithm for steiner tree

Loading...
Thumbnail Image

Access rights

openAccess

URL

Journal Title

Journal ISSN

Volume Title

A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Date

2019

Major/Subject

Mcode

Degree programme

Language

en

Pages

19
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