Fixed parameter tractability of a biconnected bottleneck Steiner network problem

For a given set X of points in the plane, we consider the problem of constructing a 2-vertex-connected network spanning X and at most k additional Steiner points such that the length of the longest edge (the so-called bottleneck) of the network is minimized. When one introduces a constraint on the network specifying that all Steiner points must be of degree 2 the problem remains NP-complete but becomes fixed parameter tractable with respect to k. We prove this by presenting an algorithm which solves the degree-2 bounded problem optimally in a time of O(n(4)k(6)2(k)), where n = |X|. We also present a simple 3-approximation algorithm for the degree-2 bounded problem and show that the bottleneck length of an optimal solution to the degree-2 bounded problem is at most twice the bottleneck length when degree is not bounded.