# Achieve global rigidity by pinning nodes

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] globally rigid in 2-dimensional space.

## Remarks

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 ^{[1]} 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 in 2-dimensional space was solved by Fekete ^{[2]} (the non-generic version of the problem can be solved by matroid matching). It was shown by Mansfield ^{[3]} that the 3-dimensional version of this problem is NP-hard.

## References

- ↑ T. Jordán,
*Rigid and Globally Rigid Graphs with Pinned Vertices*, DOI link, EGRES Technical Report No. 2009-05. - ↑ Zs. Fekete,
*Source location with rigidity and tree packing requirements*, Operations Research Letters 34, Issue 6, pp. 607-612, 2006. DOI link, EGRES Technical Report. - ↑ A. Mansfield,
*On the computational complexity of a rigidity problem*, IMA J. Appl. Math. 27 (1981), no. 4, 423-429. DOI link.