Changes

A generalized version of this problem is to find a minimum cost <math>S</math> for a given cost function. The complexity of the minimum cost version is also unknown; Tibor Jordán <ref>T. Jordán, ''Rigid and Globally Rigid Graphs with Pinned Vertices'', [http:name="Jo1"//www.cs.elte.hu/egres/tr/egres-09-05.pdf EGRES Technical Report No. 2009-05].</ref> gave an approximation algorithm with an approximation factor of 5/2.

The related problem where one looks for a minimum cardinality set of nodes to pin so as to render <math>G+K_S</math> [[Rigid graph|rigid]] in 2 dimensions was solved by Fekete <refname="Fe"/>Zs. Fekete, ''Source location with rigidity and tree packing requirements'', Operations Research Letters 34, Issue 6, pp. 607(the non-612, 2006. generic version of the problem can be solved by [http://dx.doi.org/10.1016/j.orl.2005.10.005 DOI link], [http://www.cs.elte.hu/egres/tr/egres-05-04.pdf EGRES Technical Reportmatroid matching].</ref>]). It was shown by Mansfield <ref>A. Mansfield, ''On the computational complexity of a rigidity problem'', IMA J. Appl. Math. 27 (1981), no. 4, 423-429. [http:name="Ma"//dx.doi.org/10.1093/imamat/27.4.423 DOI link].</ref> that in 3 dimensions this problem is NP-hard.