Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable

Abstract

In the Euclidean Bottleneck Steiner Tree problem, the input consists of a set of $n$ points in ${\mathbb{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 ${\mathbb{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 ${\ell }_1$ and ${\ell }_{\infty }$ variants of the problem are FPT. Our approach can be generalized to the problem with ${\ell }_p$ metric for any rational $1\le p\le \infty$, or even other metrics on ${\mathbb{R}}^2$.

In SODA'24