On the low-dimensional Steiner minimum tree problem in Hamming metric

While it is known that the d-dimensional Steiner minimum tree problem in Hamming metric is NP-complete if d is part of the input, it is an open question whether this also holds for fixed dimensions. In this paper, this question is answered by showing that the Steiner minimum tree problem in Hamming metric is already NP-complete in 3 dimensions. Furthermore, we show that, the minimum spanning tree gives a approximation on the Steiner minimum tree for d≥2. Using this result, we analyse the so-called k-LCA and Ak approximation algorithms and show improved approximation guarantees for low dimensions.