# Achieve global rigidity by pinning nodes

Given a graph $G(V,E)$, find a minimum cardinality set $S \subset V$ of nodes such that adding a complete graph on $S$ renders the graph $G+K_S$ globally rigid in 2-dimensional space.

## Remarks

A generalized version of this problem is to find a minimum cost $S$ 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 $G+K_S$ 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

1. T. Jordán, Rigid and Globally Rigid Graphs with Pinned Vertices, DOI link, EGRES Technical Report No. 2009-05.
2. 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.
3. A. Mansfield, On the computational complexity of a rigidity problem, IMA J. Appl. Math. 27 (1981), no. 4, 423-429. DOI link.