Parameterized single-exponential time polynomial space algorithm for steiner tree

Research output: Contribution to journalArticleScientificpeer-review

Researchers

  • Fedor Fomin
  • Petteri Kaski

  • Daniel Lokshtanov
  • Fahad Panolan
  • Saket Saurabh

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 languageEnglish
Pages (from-to)327-345
Number of pages19
JournalSIAM Journal on Discrete Mathematics
Volume33
Issue number1
Publication statusPublished - 2019
MoE publication typeA1 Journal article-refereed

    Research areas

  • Steiner tree, FPT algorithm, recurrence relation

Download statistics

No data available

ID: 33204502