Parameterized single-exponential time polynomial space algorithm for steiner tree

Fedor Fomin*, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

94 Downloads (Pure)


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.

Original languageEnglish
Pages (from-to)327-345
Number of pages19
JournalSIAM Journal on Discrete Mathematics
Issue number1
Publication statusPublished - 2019
MoE publication typeA1 Journal article-refereed


  • Steiner tree
  • FPT algorithm
  • recurrence relation

Cite this