\(k\)-Steiner-minimal-trees in metric spaces (Q1808781): Difference between revisions

For a given set \(N\) of points in a metric space, a Steiner-minimal tree (SMT) is a tree, connecting the points of \(N\) with minimum total length. A \(k\)-SMT is a Steiner tree, but now at most \(k\)-additional `Steiner' points (points on the tree with degree at least three that do not belong to \(N\)) may be added. The problem to find a 0-SMT is the classic shortest spanning tree problem and can be solved in linear time. On the other hand, the unrestricted Steiner tree problem is NP-hard. This paper considers the complexity of the \(k\)-Steiner tree problem, where \(k\) is a given integer (considered to be fixed). It shows that if two conditions are fulfilled, then the problem is polynomial time solvable. The first of these conditions is that there is a natural number \(c\) that only depends on the metric space, such that any Steiner point in any \(k\)-SMT has vertex degree at most \(c\), and the second condition states that for each number \(n\) between 3 and \(kc- k+1\) there is an algorithm that finds the shortest tree for each set of \(n\) points. Also, it is shown that the relative defect going from a \((k-1)\)-SMT to a \(k\)-SMT tends to zero, when \(k\) goes to infinity.