Computational complexity of the 2-connected Steiner network problem in the ℓp plane

Abstract

The geometric 2-connected Steiner network problem asks for a shortest bridgeless network spanning a given set of terminals in the plane such that the total length of all edges of the network, as measured in the ℓp metric, is a minimum. Using reduction from the problem of deciding the Hamiltonicity of planar cubic bipartite graphs we show that this problem is NP-hard (and NP-complete when discretised) for any constant p≥2 or p=1. Our reduction shows that the geometric 2-connected spanning network problem, i.e., the analogous problem without Steiner points, is also NP-hard for p≥2 or p=1.