Exact Algorithms for the Bottleneck Steiner Tree Problem

Given n points, called terminals, in the plane ℝ² and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ² and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ², usually, the Euclidean or the L 1 metric. This problem is known to be NP‐hard. In this paper, we study this problem in the L p metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed‐parameter tractable algorithm running in f(k)·nlog ² n time for the L 1 and the L ∞ metrics, and the first exact algorithm for the L p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)·(n ^k +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L 2 metric.