Changes
<onlyinclude>
Given a graph <math>G(V,E)</math>, find a minimum cardinality set <math>S \subset V</math> of nodes such that adding a complete graph on <math>S</math> renders the graph <math>G+K_S</math> [[Rigid graph|globally rigid]] in 2 dimensions.
</onlyinclude>
== Remarks ==
A generalized version of this problem is to find a minimum cost <math>S</math> for a given cost function.The brother complexity of this problem where one looks for a the minimum cardinality set of nodes to pin so as to render <math>G+K_S</math> infinitesimally rigid was solved bycost version is also unknown; Tibor Jordán<ref>T. Jordán, ''Rigid and Globally Rigid Graphs with Pinned Vertices'', [http://www.cs.elte.hu/egres/tr/egres-09-05.pdf EGRES Technical Report No. 2009-05].</ref>. In that same paper gave an approximation algorithm is given to finding the pinning set to achieve global rigidity. An with an approximation factor of 5/2 is proven also for the cost version.
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 <ref>Zs. Fekete, ''Source location with rigidity and tree packing requirements'', Operations Research Letters 34, Issue 6, pp. 607-612, 2006. [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 Report].</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://dx.doi.org/10.1093/imamat/27.4.423 DOI link].</ref> that in 3 dimensions this problem is NP-hard.
==References==
