On the Computational Complexity of a Rigidity Problem
Anthony Mansfield · IMA Journal of Applied Mathematics · 1981
Consider a structure of flexible joints connected by rigid bars. These bars will constrain the possible motions of the joints of this structure. By “pinning down” some of the joints so that they cannot move further constraints will be added. In this way the entire structure can be made rigid. A problem considered by Bolker & Crapo (1977) and others, is that of finding the minimum number of joints that must be pinned in order to make a given two- or three-dimensional structure rigid. We consider the computational complexity of this problem. Lovasz (1980) gives a somewhat complicated but polynomial time procedure for this problem in the two-dimensional case. In this paper we show that in three or more dimensions the problem is NP-complete, and so is unlikely to have a polynomial time algorithm.