Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable

In the Euclidean Bottleneck Steiner Tree problem, the input consists of a set of n points in R 2 called terminals and a parameter k, and the goal is to compute a Steiner tree that spans all the terminals and contains at most k points of R 2 as Steiner points such that the maximum edge-length of the Steiner tree is minimized, where the length of a tree edge is the Euclidean distance between its two endpoints. The problem is well-studied and is known to be NP-hard. In this paper, we give a k O(k) n O(1) -time algorithm for Euclidean Bottleneck Steiner Tree, which implies that the problem is fixed-parameter tractable (FPT). This settles an open question explicitly asked by Bae et al. [Algorithmica, 2011], who showed that the ℓ 1 and ℓ ∞ variants of the problem are FPT. Our approach can be generalized to the problem with ℓ p metric for any rational 1 ≤ p ≤ ∞, or even other metrics on R 2 .