On the Computational Complexity of a Rigidity Problem

Consider a structure of flexible joints connected by rigid bars.These bars will constrain the possible motions of the jointsof this structure. By "pinning down" some of the joints so thatthey cannot move further constraints will be added. In thisway the entire structure can be made rigid. A problem consideredby Bolker & Crapo (1977) and others, is that of findingthe minimum number of joints that must be pinned in order tomake a given two- or three-dimensional structure rigid. We considerthe computational complexity of this problem. Lovasz (1980)gives a somewhat complicated but polynomial time procedure forthis problem in the two-dimensional case. In this paper we showthat in three or more dimensions the problem is NP-complete,and so is unlikely to have a polynomial time algorithm.