The Rectilinear Steiner Tree Problem is $NP$-Complete

TLDR

An optimum rectilinear Steiner tree connects a set of points in the plane with horizontal and vertical segments of minimum total length, a structure used to model efficient net wiring on printed backplanes. The authors prove several intermediary lemmas on the NP‑completeness of related graph‑theoretic problems, which underpin the main reduction. They establish that computing the minimum length of a rectilinear Steiner tree is NP‑complete, implying that finding optimal trees is likely computationally infeasible and justifying the focus on heuristics and special‑case algorithms.

Abstract

An optimum rectilinear Steiner tree for a set A of points in the plane is a tree which interconnects A using horizontal and vertical lines of shortest possible total length. Such trees correspond to single net wiring patterns on printed backplanes which minimize total wire length. We show that the problem of determining this minimum length, given A, is $NP$-complete. Thus the problem of finding optimum rectilinear Steiner trees is probably computationally hopeless, and the emphasis of the literature for this problem on heuristics and special case algorithms is well justified. A number of intermediary lemmas concerning the $NP$-completeness of certain graph-theoretic problems are proved and may be of independent interest.