# Parameterized single-exponential time polynomial space algorithm for steiner tree

Research output: Contribution to journal › Article › Scientific › peer-review

### Researchers

### Research units

- University of Bergen
- Homi Bhabha National Institute
- University of California at Santa Barbara

### 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) . logW) and using O(n(3) . lognW . 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) logW) 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(O(f(epsilon))) logW space 4((1+epsilon)k)n(O(f(epsilon))) logW time algorithm for STEINER TREE, where f is a computable function depending only on epsilon.

### Details

Original language | English |
---|---|

Pages (from-to) | 327-345 |

Number of pages | 19 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 33 |

Issue number | 1 |

Publication status | Published - 2019 |

MoE publication type | A1 Journal article-refereed |

- Steiner tree, FPT algorithm, recurrence relation

### Research areas

### Download statistics

ID: 33204502