Fixed parameter tractability of a biconnected bottleneck Steiner network problem

Abstract

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(n4k62k), where n = |X|. We also present a simple 3-approximation algorithm for the degree-2 bounded problem and show that the bottleneck leng..