Embedding Complexity and Discrete Optimization II: A Dynamical Programming Approach to the Steiner-Tree Problem

摘要

In this note, we continue our work devoted to investigating the concept of embedding complexity (cf. Cieslik et al. [3]) and present a new Divide and Conquer algorithm for solving the Steiner-tree problem for graphs that relies on dynamic-programming schemes. In this way,we show how the rather general conceptual framework developed in our previous paper can be used even in rather awkward situations and that, more specifically, it allows us to design a treewidthbased algorithm for finding Steiner trees in a (weighted or unweighted) graph that is linear with respect to the number of the graph's vertices, yet (as we cannot avoid paying the “standard fine” set on using treewidth-based algorithms) highly exponential with respect to the graph's treewidth.