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

摘要

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 (9(1.5296") algorithm for NWST. It is also shown that Hakimi's 46-year-old algorithm for Steiner tree is essentially best-possible 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.