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.
