2023/12/04 by Bandyapadhyay, Sayan, Lochet, William, Lokshtanov, Daniel +2
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2312.01589
In the Euclidean Bottleneck Steiner Tree problem, the input consists of a set of n points in ℝ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 ℝ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 kO(k) nO(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 ℝ2.