Parameterized single-exponential time polynomial space algorithm for steiner tree

Tutkimustuotos: Lehtiartikkelivertaisarvioitu


  • Fedor Fomin
  • Petteri Kaski

  • Daniel Lokshtanov
  • Fahad Panolan
  • Saket Saurabh


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


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.


JulkaisuSIAM Journal on Discrete Mathematics
TilaJulkaistu - 2019
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Lataa tilasto

Ei tietoja saatavilla

ID: 33204502