Algorithms for node-weighted Steiner tree and maximum-weight connected subgraph

作者：Buchanan Austin^*; Wang Yiming; Butenko Sergiy

来源：Networks, 2018, 72(2): 238-248.

DOI：10.1002/net.21825

• fixed-parameter tractable
• maximum weight connected subgraph node-weighted Steiner tree
• Steiner tree
• strong exponential time hypothesis

This article considers the node-weighted Steiner tree (NWST) problem and the maximum-weight connected subgraph (MWCS) problem, which have applications in the design of telecommunication networks and the analysis of biological networks. Exact algorithms with provable worst-case runtimes are provided. The first algorithm for NWST runs in time O(n(3)) for n-vertex instances when the number of terminals is bounded. It is based on dynamic programming and generalizes a Steiner tree algorithm of Dreyfus and Wagner. When used alongside Hakimi's spanning tree enumeration algorithm, it implies a time O(1.5296(n)) algorithm for NWST. It is also shown that Hakinti's 46-year-old algorithm for Steiner tree is essentially bestpossible under the strong exponential time hypothesis (SETH). Then two algorithms for MWCS are provided. Their runtimes are polynomial in the number of vertices of the graph, but exponential in the number of vertices that have positive (or negative) weight. The latter is shown to be essentially best-possible under SETH. Together, they imply that MWCS can be solved in time O(1.5875(n)). To the best of the authors' knowledge, these are the first improvements over exhaustive search in the literature.

• 出版日期2018-9