Minimum Cost Globally Rigid Subgraphs

Tibor Jordán, András Mihálykó


A $d$-dimensional framework is a pair $(G,p)$, where $G=(V,E)$ is a graph and $p$ is a map from $V$ to $\mathbb{R}^d$. The length of an edge of $G$ is equal to the distance between the points corresponding to its end-vertices. The framework is said to be globally rigid if its edge lengths uniquely determine all pairwise distances in the framework. A graph $G$ is called globally rigid in $\mathbb{R}^d$ if every generic $d$-dimensional framework $(G,p)$ is globally rigid. Global rigidity has applications in wireless sensor network localization, molecular conformation, formation control, CAD, and elsewhere. \newline Motivated by these applications we consider the following optimization problem: given a graph $G=(V,E)$, a non-negative cost function $c:E\to \mathbb{R}_{+}$ on the edge set of $G$, and a positive integer $d$. Find a subgraph $H=(V,E')$ of $G$, on the same vertex set, which is globally rigid in $\mathbb{R}^d$ and for which the total cost $c(E'):=\sum_{e\in E'} c(e)$ of the edges is as small as possible. This problem is NP-hard for all $d\geq 1$, even if $c$ is uniform or $G$ is complete and $c$ is metric. We focus on the two-dimensional case, where we give $\frac{3}{2}$-approximation (resp. $2$-approximation) algorithms for the uniform cost and metric versions. We also develop a constant factor approximation algorithm for the metric version of the $d$-dimensional problem, for every $d\geq 3$.

Bibtex entry:

AUTHOR = {Jord{\'a}n, Tibor and Mih{\'a}lyk{\'o}, Andr{\'a}s},
TITLE = {Minimum Cost Globally Rigid Subgraphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-01}

Last modification: 29.12.2020. Please email your comments to Tamás Király!